David Eppstein - Publications

1992

• Fast optimal parallel algorithms for maximal matching in sparse graphs.
  H. Asuri, M. Dillencourt, D. Eppstein, G. Lueker, and M. Molodowitch.
  Tech. Rep. 92-01, ICS, UCI, 1992.

  We later discovered that the same results were published in a SPAA paper by Greg Shannon.

• Sets of points with many halving lines.
  D. Eppstein.
  Tech. Rep. 92-86, ICS, UCI, 1992.

  I used genetic algorithms to search for small configurations of points bisected by lines in many combinatorially distinct ways.

• Finding minimum area \(k\)-gons.
  D. Eppstein, M. Overmars, G. Rote, and G. Woeginger.
  Disc. Comp. Geom. 7 (1): 45–58, 1992.

  Uses dynamic programming to choose sets of \(k\) points optimizing various criteria on the quality of their convex hull (in particular area). The time complexity (cubic in \(n\)) was later improved to quadratic in my paper "New algorithms for minimum area \(k\)-gons", which however continues to use the same dynamic program as a subroutine.

• Simultaneous strong separations of probabilistic and unambiguous complexity classes.
  D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener.
  Int. Conf. Computing and Information, Toronto, North-Holland, 1989, pp. 65–70.
  Tech. Rep. 335, Dept. Comp. Sci., U. Rochester, 1990.
  Mathematical Systems Theory 25 (1): 23–36, 1992.

  Structural complexity theory. Constructs oracles in which \(\mathsf{BPP}\) (a probabilistic complexity class) and \(\mathsf{UP}\) (the class of problems with a unique "witness") contain languages that in a very strong sense are not contained in the other class. The conference version used the title "Probabilistic and unambiguous computation are incomparable".

• Maintenance of a minimum spanning forest in a dynamic plane graph.
  D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung.
  1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 1–11.
  J. Algorithms 13 (1): 33–54, 1992 (special issue for 1st Symp. Discrete Algorithms).
  Corrigendum, J. Algorithms 15: 173, 1993.

  The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.

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

• Parallel recognition of series parallel graphs.
  D. Eppstein.
  Information & Computation 98: 41–55, 1992.

  Characterizes two-terminal series graphs in terms of a tree-like structure in their ear decompositions. Uses this characterization to construct parallel algorithms that recognize these graphs and construct their series-parallel decompositions.

• Finding the k smallest spanning trees.
  D. Eppstein.
  2nd Scand. Worksh. Algorithm Theory, Bergen, Norway, 1990.
  Springer, Lecture Notes in Comp. Sci. 447, 1990, pp. 38–47.
  BIT 32: 237–248, 1992 (special issue for 2nd Scand. Worksh. Algorithm Theory).

  By removing edges not involved in some solution, and contracting edges involved in all solutions, we reduce the problem to one in a graph with O(k) edges and vertices. This simplification step transforms any time bound involving m or n to one involving min(m, k) or min(n, k) respectively. This paper also introduces the geometric version of the k smallest spanning trees problem (the graph version was long known) which it solves using order (k+1) Voronoi diagrams.

• Sparse dynamic programming.
  D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
  1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 513–522.
  "Sparse dynamic programming I: linear cost functions", J. ACM 39: 519–545, 1992.
  "Sparse dynamic programming II: convex and concave cost functions", J. ACM 39: 546–567, 1992.

  Considers sequence alignment and RNA structure problems in which the solution is constructed by piecing together some initial set of fragments (e.g. short sequences that match exactly). The method is to consider a planar point set formed by the fragment positions in the two input sequences, and use plane sweep to construct a cellular decomposition of the plane similar to the rectilinear Voronoi diagram.

• Polynomial-size non-obtuse triangulation of polygons.
  M. Bern and D. Eppstein.
  7th ACM Symp. Comp. Geom., North Conway, New Hampshire, 1991, pp. 342–350.
  Int. J. Comp. Geom. & Appl. 2: 241–255, 1992 (special issue for 7th Symp. Comput. Geom.).

  Any simple polygon can be triangulated with quadratically many nonobtuse triangles. Mostly subsumed by recent results of Bern et al described in "Faster circle packing".

• Connectivity, graph minors, and subgraph multiplicity.
  D. Eppstein.
  Tech. Rep. 92-06, ICS, UCI, 1992.
  J. Graph Th. 17: 409–416, 1993.

  It was known that planar graphs have \(O(n)\) subgraphs isomorphic to \(K_3\) or \(K_4\). That is, \(K_3\) and \(K_4\) have linear subgraph multiplicity. This paper shows that the graphs with linear subgraph multiplicity in the planar graphs are exactly the 3-connected planar graphs. Also, the graphs with linear subgraph multiplicity in the outerplanar graphs are exactly the 2-connected outerplanar graphs.

  More generally, let \(\mathcal{F}\) be a minor-closed family, and let \(x\) be the smallest number such that some complete bipartite graph \(K_{x,y}\) is a forbidden minor for \(\mathcal{F}\). Then the \(x\)-connected graphs have linear subgraph multiplicity for \(\mathcal{F}\), and there exists an \((x-1)\)-connected graph (namely \(K_{x-1,x-1}\) that does not have linear subgraph multiplicity. When \(x\le 3\) or when \(x=4\) and the minimal forbidden minors for \(\mathcal{F}\) are triangle-free, then the graphs with linear subgraph multiplicity for \(\mathcal{F}\) are exactly the \(x\)-connected graphs.

  Please refer only to the journal version, and not the earlier technical report: the technical report had a bug that was repaired in the journal version.

• Edge insertion for optimal triangulations.
  M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T.S. Tan.
  1st Latin Amer. Symp. Theoretical Informatics, Sao Paulo, 1992.
  Springer, Lecture Notes in Comp. Sci. 583, 1992, pp. 46–60.
  Tech. Rep. EDC UILU-ENG-92-1702, Univ. Illinois, Urbana-Champaign, 1992.
  Disc. & Comp. Geom. 10: 47–65, 1993.

  One standard way of constructing Delaunay triangulations is by iterated local improvement, in which each step flips the diagonal of some quadrilateral. For many other optimal triangulation problems, flipping is insufficient, but the problems can instead be solved by a more general local improvement step in which a new edge is added to the triangulation, cutting through several triangles, and the region it cuts through is retriangulated on both sides.

• Dynamic three-dimensional linear programming.
  D. Eppstein.
  Tech. Rep. 91-53, ICS, UCI, 1991.
  32nd IEEE Symp. Foundations of Comp. Sci., San Juan, Puerto Rico, 1991, pp. 488–494.
  ORSA J. Computing 4: 360–368, 1992 (special issue on computational geometry).

  Uses Dobkin-Kirkpatrick hierarchies to perform linear programming queries in the intersection of several convex polyhedra. By maintaining a collection of halfspaces as several subsets, represented by polyhedra, this leads to algorithms for a dynamic linear program in which updates change the set of constraints. The fully dynamic results have largely been subsumed by Agarwal and Matoušek, but this paper also includes polylog time results for semi-online problems, and uses them to give a fast randomized algorithm for the planar 2-center problem (later improved by various authors, most recently in "Faster Construction of Planar Two-Centers", which re-uses the data structures described here).

• Approximating the minimum weight Steiner triangulation.
  D. Eppstein.
  Tech. Rep. 91-55, ICS, UCI, 1991.
  3rd ACM-SIAM Symp. Discrete Algorithms, Orlando, 1992, pp. 48–57.
  Disc. Comp. Geom. 11: 163–191, 1994.

  Quadtree based triangulation gives a large but constant factor approximation to the minimum weight triangulation of a point set or convex polygon, allowing extra Steiner points to be added as vertices. Includes proofs of several bounds on triangulation weight relative to the minimum spanning tree or non-Steiner triangulation, and a conjecture that for convex polygons the only points that need to be added are on the polygon boundary.

• New algorithms for minimum area k-gons.
  D. Eppstein.
  Tech. Rep. 91-59, ICS, UCI, 1991.
  3rd ACM-SIAM Symp. Discrete Algorithms, Orlando, 1992, pp. 83–86.

  Shows that the minimum area polygon containing k of n points must be near a line determined by two points, and uses this observation to find the polygon quickly. Merged with "Iterated nearest neighbors and finding minimal polytopes" in the journal version.

• New algorithms for minimum measure simplices and one-dimensional weighted Voronoi diagrams.
  D. Eppstein and J. Erickson.
  Tech. Rep. 92-55, ICS, UCI, 1992.

  Looks at space complexity of finding minimum simplices – solves the problem in O(n²) space and O(n^d) time (matching the best known time bounds) or in linear space at the expense of an additional log in time. Also finds one-dimensional multiplicatively weighted Voronoi diagrams in linear time for sorted inputs (O(n log n) was known).

• Iterated nearest neighbors and finding minimal polytopes.
  D. Eppstein and J. Erickson.
  Tech. Rep. 92-71, ICS, UCI, 1992.
  4th ACM-SIAM Symp. Discrete Algorithms, Austin, 1993, pp. 64–73.
  Disc. Comp. Geom. 11: 321–350, 1994.

  Showed that for various optimization criteria, the optimal polygon containing k of n points must be near one of the points, hence one can transform time bounds involving several factors of n to bounds linear in n but polynomial in k. Used as a subroutine are data structures for finding several nearest neighbors in rectilinear metric spaces, and algorithms for finding the deepest point in an arrangement of cubes or spheres.

• Tree-weighted neighbors and geometric k smallest spanning trees.
  D. Eppstein.
  Tech. Rep. 92-77, ICS, UCI, 1992.
  Int. J. Comp. Geom. & Appl. 4: 229–238, 1994.

  "Finding the k smallest spanning trees" used higher order Voronoi diagrams to reduce the geometric k smallest spanning tree problem to the graph problem. Here I instead use nearest neighbors for a modified distance function where the bottleneck shortest path length is subtracted from the true distance between points. The result improves the planar time bounds and extends more easily to higher dimensions.

• Offline algorithms for dynamic minimum spanning tree problems.
  D. Eppstein.
  2nd Worksh. Algorithms and Data Structures, Ottawa, Canada, 1991.
  Springer, Lecture Notes in Comp. Sci. 519, 1991, pp. 392–399.
  Tech. Rep. 92-04, ICS, UCI, 1992.
  J. Algorithms 17: 237–250, 1994.

  Given a sequence of edge insertions and deletions in a graph, finds the corresponding sequence of minimum spanning tree changes, in logarithmic time per update. Similarly solves the planar geometric version of the problem (using a novel "mixed MST" formulation in which part of the input is a graph and part is a point set) in time \(O(\log^2 n)\) for the Euclidean metric and \(O(\log n\log\log n)\) for the rectilinear metric.

• Dynamic Euclidean minimum spanning trees and extrema of binary functions.
  D. Eppstein.
  Tech. Rep. 92-05, ICS, UCI, 1992.
  Tech. Rep. 92-88, ICS, UCI, 1992.
  Disc. Comp. Geom. 13: 111–122, 1995.

  Shows that bichromatic nearest neighbors can be maintained under point insertion and deletion essentially as quickly as known solutions to the post office problem, and that the minimum spanning tree can be maintained in the same time except for an additive O(sqrt n) needed for solving the corresponding graph problem. TR 92-88's title was actually "Fully dynamic maintenance of Euclidean minimum spanning trees and maxima of decomposable functions". TR 92-05's title left out the part about maxima; that version gave a slower algorithm superseded by the result in 92-88.

• Dynamic algorithms for half-space reporting, proximity problems, and geometric minimum spanning trees.
  P.K. Agarwal, D. Eppstein, and J. Matoušek.
  33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 80–89.

  This conference paper merged my results from "Dynamic Euclidean minimum spanning trees" with results of my co-authors on nearest neighbors and halfspace range searching.

• Asymptotic speed-ups in constructive solid geometry.
  D. Eppstein.
  Tech. Rep. 92-87, ICS, UCI, 1992.
  Algorithmica 13: 462–471, 1995.

  Finds boundary representations of CSG objects. Uses techniques from dynamic graph algorithms, including a tree partitioning technique of Frederickson and a new data structure for maintaining the value of a Boolean expression with changing variables in time O(log n / log log n) per update.

• Triangulating polygons without large angles.
  M. Bern, D. Dobkin, and D. Eppstein.
  8th ACM Symp. Comp. Geom., Berlin, 1992, pp. 222–231.
  Int. J. Comp. Geom. & Appl. 5: 171–192, 1995 (special issue for 8th Symp. Comput. Geom.)

  Follows up "Polynomial size non-obtuse triangulation of polygons"; improves the number of triangles by relaxing the requirements on their angles. Again mostly subsumed by results of Bern et al described in "Faster circle packing".

• Mesh generation and optimal triangulation.
  M. Bern and D. Eppstein.
  Tech. Rep. CSL-92-1, Xerox PARC, 1992.
  Computing in Euclidean Geometry, D.-Z. Du and F.K. Hwang, eds., World Scientific, 1992, pp. 23–90.
  Revised version in Computing in Euclidean Geometry, 2nd ed., D.-Z. Du and F.K. Hwang, eds., World Scientific, 1995, pp. 47–123.

  Considers both heuristics and theoretical algorithms for finding good triangulations and tetrahedralizations for surface interpolation and unstructured finite element meshes. Note that the online copy here omits the figures.

• 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\).

• The diameter of nearest neighbor graphs.
  D. Eppstein.
  Tech. Rep. 92-76, ICS, UCI, 1992.

  Any connected nearest neighbor forest with diameter D has O(D⁶) vertices. This was later further improved to O(D⁵) and merged with results of Paterson and Yao into "On nearest neighbor graphs".