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

(BibTeX -- Citations -- CiteSeer -- ACM DL)

**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.(BibTeX -- Full paper -- Citations -- CiteSeer -- ACM DL)

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

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

**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.(BibTeX -- Citations -- CiteSeer -- ACM DL)

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

(BibTeX -- Citations -- SCG paper -- SCG talk slides -- CiteSeer -- ACM DL (CGTA))

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

**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.(BibTeX -- Citations -- ACM DL)

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

(BibTeX -- Erik's publication page -- CiteSeer -- ACM DL)

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

(BibTeX -- Erik's CCCG publication page -- Erik's CGTA publication page -- Citations)

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

(BibTeX)

**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^{2}n). The unconstrained center placement algorithm involves quasiconvex programming, and is used as a subroutine in the constrained center placement algorithm.(SoCG05 talk slides -- Citations -- BibTeX)

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

*Lecture Notes in Comp. Sci.*4619, 2007, pp. 77-88, © Springer-Verlag.

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.

**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*, in press (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.

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

Semi-automatically filtered from a common source file.