David Eppstein - Publications

Computational Geometry : Theory & Applications

• The farthest point Delaunay triangulation minimizes angles.
  D. Eppstein.
  Tech. Rep. 90-45, ICS, UCI, 1990.
  Comp. Geom. Theory & Applications 1: 143–148, 1992.

  Given a collection of points in convex position, the sharpest angle determined by any triple can be found as a corner of a triangle in the farthest point Delaunay triangulation.

• 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.

  (Full paper)

• Average case analysis of dynamic geometric optimization.
  D. Eppstein.
  Tech. Rep. 93-18, ICS, UCI, 1993.
  5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 77–86.
  Comp. Geom. Theory & Applications 6: 45–68, 1996.

  The Tech. Report used the more informative title "Updating widths and maximum spanning trees using the rotating caliper graph", which I also used for the journal submission, but the referees made me change it back. Dynamic geometry in a model of Mulmuley and Schwarzkopf in which insertions and deletions are chosen randomly among a worst-case pool of points. This paper introduces several fundamental techniques including the rotating caliper graph of a point set and a method for performing decomposible range queries in the average case setting. It has also since inspired the use of a similar model in dynamic graph algorithms.

  (SODA paper – Full paper)

• Faster geometric k-point MST approximation.
  D. Eppstein.
  Tech. Rep. 95-13, ICS, UCI, 1995.
  Comp. Geom. Theory & Applications 8: 231–240, 1997.

  Various authors have looked at a variant of geometric clustering in which one must select k points that can be connected by a small spanning tree. The problem is NP-complete (for variable k); good approximations are known based on dynamic programming techniques but the time dependence on n is high. This paper describes a faster approximation algorithm based on dynamic programming in quadtrees, and a general technique based on that in "Iterated nearest neighbors" for reducing the dependence on n in any approximation algorithm.

• Linear complexity hexahedral mesh generation.
  D. Eppstein.
  Tech. Rep. 95-51, ICS, UCI, 1995.
  12th ACM Symp. Comp. Geom., Philadelphia, 1996, pp. 58–67.
  arXiv:cs.CG/9809109.
  Comp. Geom. Theory & Applications 12: 3–16, 1999 (special issue for 12th SCG).

  Any simply connected polyhedron with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face.

  (SCG paper – SCG talk slides)

• 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.

  (Preprint of journal version with legible figures)

• Beta-skeletons have unbounded dilation.
  D. Eppstein.
  Tech. Rep. 96-15, ICS, UCI, 1996.
  arXiv:cs.CG/9907031.
  Comp. Geom. Theory & Applications 23: 43–52, 2002.

  Beta-skeletons are geometric graphs used among other purposes for empirical network analysis and minimum weight triangulation. A fractal construction shows that, for any beta>0, the beta-skeleton of a point set can have arbitrarily large dilation: Omega(n^c), where c is a constant depending on beta and going to zero in the limit as beta goes to zero. In particular this applies to the Gabriel graph. We also show upper bounds on dilation of the same form.

• Ununfoldable polyhedra.
  M. Bern, E. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Snoeyink.
  arXiv:cs.CG/9908003.
  Tech. rep. CS-99-04, Univ. of Waterloo, Dept. of Computer Science, Aug. 1999.
  11th Canad. Conf. Comp. Geom., 1999.
  4th CGC Worksh. Computational Geometry, Johns Hopkins Univ., 1999.
  Comp. Geom. Theory & Applications (special issue for 4th CGC Worksh.) 24 (2): 51–62, 2003.

  We prove the existence of polyhedra in which all faces are convex, but which can not be cut along edges and folded flat.

  Note variations in different versions: the CCCG one was only Bern, Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable polyhedra with triangular faces". The journal version uses the title "Ununfoldable polyhedra with convex faces" and the combined results from both conference versions.

• Hinged dissections of polyominos and polyforms.
  E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.
  arXiv:cs.CG/9907018.
  11th Canad. Conf. Comp. Geom., 1999.
  Computational Geometry: Theory and Applications 31 (3): 237–262, 2005 (special issue for 11th CCCG).

  We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.

• Tiling space and slabs with acute tetrahedra.
  D. Eppstein, J. M. Sullivan, and A. Üngör.
  arXiv:cs.CG/0302027.
  Comp. Geom. Theory & Applications 27 (3): 237–255, 2004.

  We show it is possible to triangulate three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 77.08 degrees, and another which tiles a slab in space.

• Minimum dilation stars.
  D. Eppstein and K. Wortman.
  arXiv:cs.CG/0412025.
  21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 321–326.
  Comp. Geom. Theory & Applications 37 (1): 27–37, 2007.

  We show how to test the dilation of a star, embedded in a Euclidean space of bounded dimension, in time O(n log n), and how to find the star center that has the minimum dilation for a given set of leaf points in randomized expected time O(n log n). For two-dimensional points, we can find the minimum dilation center, constrained to be one of the input points, in time O(n 2^α(n) log²n). The unconstrained center placement algorithm involves quasiconvex programming, and is used as a subroutine in the constrained center placement algorithm.

  (SoCG05 talk slides)

• Drawings of planar graphs with few slopes and segments.
  V. Dujmović, D. Eppstein, M. Suderman, and D. R. Wood.
  arXiv:math.CO/0606450.
  Comp. Geom. Theory & Applications 38: 194–212, 2007.

  We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 5n/2 segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface).

• Edges and switches, tunnels and bridges.
  D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann.
  23rd European Workshop on Computational Geometry (EWCG'07), Graz, 2007.
  10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
  Springer, Lecture Notes in Comp. Sci. 4619, 2007, pp. 77–88.
  Tech. Rep. UU-CS-2007-042, Utrecht Univ., Dept. of Information and Computing Sciences, 2007.
  arXiv:0705.0413.
  Comp. Geom. Theory & Applications 42 (8): 790–802, 2009 (special issue for EWCG'07).

  We show how to solve several versions of the problem of casing graph drawings: that is, given a drawing, choosing to draw one edge as upper and one lower at each crossing in order to improve the drawing's readability.

  (WADS talk slides)

• Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets.
  G. Borradaile and D. Eppstein.
  arXiv:1206.2254.
  24th Canadian Conference on Computational Geometry (CCCG 2012), Prince Edward Island, Canada, 2012, pp. 311–316.
  Comp. Geom. Theory & Applications 49: 8–16, 2015 (special issue for CCCG 2012).

  When a planar point set has the property that its Delaunay triangulation has no large angles, we show how to connect it by a plane graph (having linearly many additional Steiner vertices) in which the distances between the original points are approximations to their Euclidean distance, and in which the total graph weight is at most a constant times the minimum spanning tree weight. The time to construct this graph is near-linear, the same as for integer sorting. We use this result to approximate the traveling salesman problem, for these point sets, in the same time bound.

• Distance-sensitive point location made easy.
  B. Aronov, M. De Berg, D. Eppstein, M. Roeloffzen, and B. Speckmann.
  30th European Workshop on Computational Geometry (EuroCG 2014), Dead Sea, Israel, March 2014.
  arXiv:1602.00767
  Comp. Geom. Theory & Applications 54: 17–31, 2016.

  We use quadtrees to handle point location queries in an amount of time that depends on the distance of the query point to the nearest region boundary.

• Ununfoldable Polyhedra with 6 Vertices or 6 Faces.
  H. A. Akitaya, E. Demaine, D. Eppstein, T. Tachi, and R. Uehara.
  22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG³), Tokyo, Japan, 2019, pp. 27–28.
  Comp. Geom. Theory & Applications 103: 101857, 2022.
  

  We find a (nonconvex, but topologically equivalent to convex) polyhedron with seven vertices and six faces that cannot be unfolded to a flat polygon by cutting along its edges. Both the number of vertices and the number of faces are the minimum possible. The JCDCG³ version used the title "Minimal ununfoldable polyhedron".

• Geometric dominating sets – A minimum version of the no-three-in-line problem.
  O. Aichholzer, D. Eppstein, and E.-M. Hainzl.
  37th European Workshop on Computational Geometry (EuroCG 2021), pp. 17:1–17:7.
  arXiv:2203.13170.
  Comp. Geom. Theory & Applications 108: 101913, 2023 (special issue for EuroCG).
  

  We study how few points can be placed in a grid so that all remaining grid points are collinear with two of the placed points.

• Angles of arc-polygons and Lombardi drawings of cacti.
  D. Eppstein, D. Frishberg, and M. Osegueda.
  arXiv:2107.03615.
  Proc. 33rd Canadian Conference on Computational Geometry, 2021, pp. 56–64.
  Comp. Geom. Theory & Applications 112: 101982, 2023 (special issue for CCCG 2021).
  

  We precisely characterize the triples vertex angles that are possible for arc-triangles (curved triangles made from circular arcs), and prove an existence theorem for a large class of sets of angles for arc-polygons. Our characterization allows us to prove that every cactus graph has a planar Lombardi drawing for its natural planar embedding (the embedding in which each cycle is a bounded face), but that there exist other embeddings of cacti that have no Lombardi drawing.