**Separator based sparsification I: planarity testing and minimum spanning trees**.

D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.

*J. Comp. Sys. Sci.*52: 3–27, 1996 (special issue for 25th STOC).First half of journal version of Separator based sparsification for dynamic planar graph algorithms.

**Separator based sparsification II: edge and vertex connectivity**.

D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.

Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.

*SIAM J. Computing*28 (1): 341–381, 1999.Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.

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

(SODA paper – Full paper)

**Computing the discrepancy with applications to supersampling patterns**.

D. P. Dobkin, D. Eppstein, and D. P. Mitchell.

*ACM Trans. on Graphics*15 (4): 354–376, 1996.Combines "Computing the discrepancy" with experimental results of Mitchell on the discrepancies of various point sets, emphasizing the application of low-discrepancy sets to anti-aliasing in raytraced graphics.

**Approximating center points with iterated Radon points**.

K. Clarkson, D. Eppstein, G.L. Miller, C. Sturtivant, and S.-H. Teng.

*9th ACM Symp. Comp. Geom.,*San Diego, 1993, pp. 91–98.

*Int. J. Comp. Geom. & Appl.*6 (3): 357–377, 1996.Given a collection of

*n*sites, a center point is a point (not necessarily a site) such that no hyperplane through the centerpoint partitions the collection into a very small and a very large subset. Center points have been used by Teng and others as a key step in the construction of geometric separators. One can find a point with this property by choosing a random sample of the collection and applying linear programming, but the complexity of that method grows exponentially with the dimension. This paper proposes an alternate method that produces lower quality approximations (in terms of the size of the worst hyperplane partition) but takes time polynomial in both*n*and*d.***Approximation algorithms for geometric problems**.

M. Bern and D. Eppstein.

*Approximation Algorithms for NP-hard Problems*, D. Hochbaum, ed., PWS Publishing, 1996, pp. 296–345.Considers problems for which no polynomial-time exact algorithms are known, and concentrates on bounds for worst-case approximation ratios, especially those depending intrinsically on geometry rather than on more general graph theoretic or metric space formulations. Includes sections on the traveling salesman problem, Steiner trees, minimum weight triangulation, clustering, and separation problems.

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

**Zonohedra and Zonotopes**.

D. Eppstein.

Tech. Rep. 95-53, ICS, UCI, 1995.

*Mathematica in Education and Research*5 (4): 15–21, 1996.I use Mathematica to construct zonotopes and display zonohedra. Many examples are shown, including one used for a lower bound in "The centroid of points with approximate weights". This paper is also available in HTML and

*Mathematica*notebook formats.**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.

(SCG paper – Full paper)

**Using sparsification for parametric minimum spanning tree problems**.

D. Fernández-Baca, G. Slutzki, and D. Eppstein.

*5th Scand. Worksh. Algorithm Theory,*Reykjavik, 1996.

Springer,*Lecture Notes in Comp. Sci.*1097, 1996, pp. 149–160.

*Nordic J. Computing*3 (4): 352–366, 1996 (special issue for 5th SWAT).Given a graph with edge weights that are linear functions of a parameter, finds the sequence of minimum spanning trees produced as the parameter varies, in total time O(mn log n), by combining ideas from "Sparsification" and "Geometric lower bounds". Also solves various problems of optimizing the parameter value, including one closely related to that in "Choosing subsets with maximum weighted average".

**Faster construction of planar two-centers**.

D. Eppstein.

Tech. Rep. 96-12, ICS, UCI, 1996.

*8th ACM-SIAM Symp. Discrete Algorithms,*New Orleans, 1997, pp. 131–138.Improving on a recent breakthrough of Sharir, we use data structures from "Dynamic three-dimensional linear programming" to find two circular disks of minimum radius covering a set of points in the Euclidean plane, in randomized expected time O(

*n*log^{2}*n*).(SODA paper – DREI and SODA talk slides)

**Dynamic connectivity in digital images**.

D. Eppstein.

Tech. Rep. 96-13, ICS, UCI, 1996.

*Inf. Proc. Lett.*62: 121–126, 1997.Any algorithm that maintains the connected components of a bitmap image must take Omega(log

*n*/ log log*n*) time per change to the image. The problem can be solved in O(log*n*) time per change using dynamic planar graph techniques. We discuss applications to computer Go and other games.**On the parity of graph spanning tree numbers**.

D. Eppstein.

Tech. Rep. 96-14, ICS, UCI, 1996.Any bipartite Eulerian graph, any Eulerian graph with evenly many vertices, and any bipartite graph with evenly many vertices and edges, has an even number of spanning trees. More generally, a graph has evenly many spanning trees if and only if it has an Eulerian edge cut.

**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.**Spanning trees and spanners**.

D. Eppstein.

Tech. Rep. 96-16, ICS, UCI, 1996.

*Handbook of Computational Geometry,*J.-R. Sack and J. Urrutia, eds., Elsevier, 1999, pp. 425–461.Surveys results in geometric network design theory, including algorithms for constructing minimum spanning trees and low-dilation graphs.

**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.**Dynamic graph algorithms**.

D. Eppstein, Z. Galil, and G.F. Italiano.

Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.

*Algorithms and Theoretical Computing Handbook,*M. J. Atallah, ed., CRC Press, 1999, chapter 8.

2nd. ed., CRC Press, 2010, Vol. I: General Concepts and Techniques, chapter 9, pp. 9–1 - 9-28.

Years – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.