**Sparsification—A technique for speeding up dynamic graph algorithms**.

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

*33rd IEEE Symp. Foundations of Comp. Sci.,*Pittsburgh, 1992, pp. 60–69.

Tech. Rep. RC 19272 (83907), IBM, 1993.

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

*J. ACM*44 (5): 669–696, 1997.Uses a divide and conquer on the edge set of a graph, together with the idea of replacing subgraphs by sparser certificates, to make various dynamic algorithms as fast on dense graphs as they are on sparse graphs. Applications include random generation of spanning trees as well as finding the

*k*minimum weight spanning trees for a given parameter*k.***Faster circle packing with application to nonobtuse triangulation**.

D. Eppstein.

Tech. Rep. 94-33, ICS, UCI 1994.

*Int. J. Comp. Geom. & Appl.*7 (5): 485–491, 1997.Speeds up a triangulation algorithm of Bern et al. ["Linear-Size Nonobtuse Triangulation of Polygons"] by finding a collection of disjoint circles which connect up the holes in a non-simple polygon. The method is to use a minimum spanning tree to find a collection of overlapping circles, then shrink them one by one to reduce the number of overlaps, using Sleator and Tarjan's dynamic tree data structure to keep track of the connectivity of the shrunken circles.

**Minimum range balanced cuts via dynamic subset sums**.

D. Eppstein.

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

*J. Algorithms*23: 375–385, 1997.Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.

**Choosing subsets with maximum weighted average**.

D. Eppstein and D. S. Hirschberg.

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

*5th MSI Worksh. on Computational Geometry*, 1995, pp. 7–8.

*J. Algorithms*24: 177–193, 1997.Uses geometric optimization techniques to find, among

*n*weighted values, the*k*to drop so as to maximize the weighted average of the remaining values. The feasibility test for the corresponding decision problem involves*k*-sets in a dual line arrangement.**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.**On nearest-neighbor graphs**.

D. Eppstein, M. S. Paterson, and F. F. Yao.

*Disc. Comp. Geom.*17: 263–282, 1997.Paterson and Yao presented a paper at ICALP showing among other things that any connected nearest neighbor forest with diameter

*D*has O(*D*^{9}) vertices. This paper is the journal version; my contribution consists of improving that bound to O(*D*^{5}), which is tight.**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.**Optimal point placement for mesh smoothing**.

N. Amenta, M. Bern, and D. Eppstein.

*8th ACM-SIAM Symp. Discrete Algorithms,*New Orleans, 1997, pp. 528–537.

Symp. Computational Geometry Approaches to Mesh Generation, SIAM 45th Anniversary Mtg., Stanford, 1997.

arXiv:cs.CG/9809081.

*J. Algorithms*30: 302–322, 1999 (special issue for SODA 1997).We study finite element mesh smoothing problems in which we move vertex locations to optimize the shapes of nearby triangles. Many such problems can be solved in linear time using generalized linear programming; we also give efficient algorithms for some non-LP-type mesh smoothing problems. One lemma may be of independent interest: the locus of points in R

^{d}from which a d-1 dimensional convex set subtends a given solid angle is convex.**An efficient algorithm for shortest paths in vertical and horizontal segments**.

D. Eppstein and D. Hart.

*5th Worksh. Algorithms and Data Structures,*Halifax, Nova Scotia, 1997.

Springer,*Lecture Notes in Comp. Sci.*1272, 1997, pp. 234–247.We show how to find shortest paths along the segments of an arrangement of

*n*vertical and horizontal line segments in the plane, in time O(*n*^{3/2}).**Guest editor's forward to special issue of papers from the 34th Annual Symposium on Foundations of Computer Science**.

D. Eppstein.

*J. Comp. Sys. Sci.*54:263, 1997.**Computational geometry and parametric matroid optimization**.

D. Eppstein.

Invited talk, 5th Int. Symp. Parametric Optimization, Chiba, Japan, 1997.This talk surveys some connections from computational geometry to parametric matroids: the results of my paper "Geometric lower bounds", new upper bounds from a paper by Tamal Dey, and a problem from constructive solid geometry with the potential to lead to stronger lower bounds.

**Quadrilateral meshing by circle packing**.

M. Bern and D. Eppstein.

*2nd CGC Worksh. Computational Geometry*, Durham, North Carolina, 1997.

*6th Int. Meshing Roundtable,*Park City, Utah, 1997, pp. 7–19.

arXiv:cs.CG/9908016.

*Int. J. Comp. Geom. & Appl.*10 (4): 347–360, 2000.We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types:

- The elements form the cells of a Voronoi diagram,
- The elements each have two opposite 90 degree angles,
- All elements are kites, or
- All angles are at most 120 degrees.

*n*). The 120-degree bound is optimal; if a simply-connected region has all angles at least 120 degrees, any mesh of that region has a 120 degree angle.

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

Semi-automatically filtered from a common source file.