**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.**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, to appear.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.

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

Semi-automatically filtered from a common source file.