David Eppstein - Publications

Papers with Matt Dickerson

• Algorithms for proximity problems in higher dimensions.
  M. T. Dickerson and D. Eppstein.
  Comp. Geom. Theory & Applications 5:277-291, 1996.

  Combines a method from "Provably good mesh generation" for finding sparse high-dimensional Delaunay triangulations, a method of Dickerson, Drysdale, and Sack ["Simple algorithms for enumerating interpoint distances", IJCGA 1992] for using Delaunay triangulations to search for nearest neighbors, and a method of Frederickson for speeding up tree-based searches. The results are fast algorithms for several proximity problems such as finding the k nearest neighbors to each point in a given point set.

  (BibTeX -- Full paper -- Citations -- CiteSeer -- ACM DL)

• On triangulating three-dimensional polygons.
  G. Barequet, M. Dickerson, and D. Eppstein.
  12th ACM Symp. Comp. Geom., Philadelphia, 1996, pp. 38-47.
  Comp. Geom. Theory & Applications 10:155-170, 1998.

  It is NP-complete, given a simple polygon in 3-space, to find a triangulated simply-connected surface (without extra vertices) spanning that polygon. If extra vertices are allowed, or the surface may be curved, such a surface exists if and only if the polygon is unknotted; the complexity of testing knottedness remains open. Snoeyink has shown that exponentially many extra vertices may be required for a triangulated spanning disk.

  (BibTeX -- SCG paper -- Full paper -- Citations -- CiteSeer -- ACM DL)

• Confluent drawings: visualizing non-planar diagrams in a planar way.
  M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
  arxiv:cs.CG/0212046.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Lecture Notes in Comp. Sci. 2912, 2004, pp. 1-12, © Springer-Verlag.
  J. Graph Algorithms and Applications (special issue for GD'03) 9(1):31-52, 2005.

  We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.

  (BibTeX -- Citations -- GDEA)

Co-authors -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.