David Eppstein - Publications

Publications with Gill Barequet

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

• Application Challenges to Computational Geometry.
  The Computational Geometry Impact Task Force Report.
  Tech. Rep. TR-521-96, Princeton University, April 1996.
  Advances in Discrete and Computational Geometry – Proc. 1996 AMS-IMS-SIAM Joint Summer Research Conf. Discrete and Computational Geometry: Ten Years Later, Contemporary Mathematics 223, Amer. Math. Soc., 1999, pp. 407–423.
  
• Straight skeletons of three-dimensional polyhedra.
  G. Barequet, D. Eppstein, M. T. Goodrich, and A. Vaxman.
  arXiv:0805.0022.
  Proc. 16th European Symp. Algorithms, Karlsruhe, Germany, 2008.
  Springer, Lecture Notes in Comp. Sci. 5193, 2008, pp. 148–160.

  A straight skeleton is defined by the locus of points crossed by the edges and vertices of a polyhedron as it undergoes a continuous shrinking process in which the faces move inwards at constant speed. We resolve some ambiguities in the definition of these shapes, define efficient algorithms for polyhedra with axis-parallel faces, show that arbitrary polyhedra have strictly more complicated straight skeletons, and report on results from an implementation of our algorithm for arbitrary polyhedra.

• On 2-site Voronoi diagrams under geometric distance functions.
  G. Barequet, M. Dickerson, D. Eppstein, D. Hodorkovsky, and K. Vyatkina.
  27th Eur. Worksh. Comp. Geom., Antoniushaus Morschach, Switzerland, 2011, pp. 59–62.
  Proc. 8th Int. Symp. Voronoi Diagrams in Science and Engineering, Qing Dao, China, 2011, pp. 31–38.
  arXiv:1105.4130.
  J. Computer Science and Technology 28 (2): 267–277, 2013.

  We study the combinatorial complexity of generalized Voronoi diagrams that determine the closest two point sites to a query point, where the distance from the query point to a pair of sites is a combination of the individual distances to the sites and the distance from one site in the pair to the other.

• Stable-matching Voronoi diagrams: combinatorial complexity and algorithms.
  G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.
  arXiv:1804.09411
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 89:1–89:14.
  J. Computational Geometry 11 (1): 26–59, 2020.

  The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.