David Eppstein - Publications

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

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

Semi-automatically filtered from a common source file.