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.

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

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

  (Citations)

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

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

Semi-automatically filtered from a common source file.