David Eppstein - Publications

ACM-SIAM Symp. Discrete Algorithms (SODA)

The Hypertext Bibliography Project at MIT also includes listings of my SODA papers.

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

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

• Visibility with a moving point of view.
  M. Bern, D.P. Dobkin, D. Eppstein, and R. Grossman.
  1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 107–118.
  Algorithmica 11: 360–378, 1994.

  An investigation of 3d visibility problems in which the viewing position moves along a straight flight path, with various assumptions on the complexity of the viewed scene.

• Efficient sequential and parallel algorithms for computing recovery points in trees and paths.
  M. Chrobak, D. Eppstein, G.F. Italiano, and M. Yung.
  2nd ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1991, pp. 158–167.
  ALCOM Report 91-74, University of Rome, 1991.

  Described slightly superlinear algorithms for partitioning a tree into a given number of subtrees, making them all as short as possible. Frederickson at the same conference further improved the sequential time to linear. There may still be something worth publishing in the parallel algorithms.

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

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

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

• Clustering for faster network simplex pivots.
  D. Eppstein.
  Tech. Rep. 93-19, ICS, UCI, 1993.
  5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 160–166.
  Networks 35 (3): 173–180, 2000.

  Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.

• Dihedral bounds for mesh generation in high dimensions.
  M. Bern, L.P. Chew, D. Eppstein, and J. Ruppert.
  892nd Meeting Amer. Math. Soc., Brooklyn, 1994.
  Abstract in Abs. Amer. Math. Soc. 15, 1994, p. 366.
  6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 189–196.

  Any d-dimensional point set can be triangulated with O(n^ceil(d/2)) simplices, none of which has an obtuse dihedral angle. No bound depending only on n is possible if we require the maximum dihedral angle to measure at most 90-epsilon degrees or the minimum dihedral to measure at least epsilon. Includes a classification of simplices in terms of their bad angles.

  (SODA paper)

• Subgraph isomorphism in planar graphs and related problems.
  D. Eppstein.
  Tech. Rep. 94-25, ICS, UCI, 1994.
  6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 632–640.
  arXiv:cs.DS/9911003.
  J. Graph Algorithms and Applications 3 (3): 1–27, 1999.

  Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper, "Diameter and treewidth in minor-closed graph families", presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.

• 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² n).

  (SODA paper – DREI and SODA talk slides)

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

  (SODA paper)

• Fast hierarchical clustering and other applications of dynamic closest pairs.
  D. Eppstein.
  9th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1998, pp. 619–628.
  arXiv:cs.DS/9912014.
  J. Experimental Algorithmics 5 (1): 1–23, 2000.

  This paper shows how to use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" for some non-geometric problems including hierarchical clustering, greedy matching, and TSP heuristics. Experiments show variants of my data structures to be faster than previously used heuristics.

  (Source code and experimental data – SODA paper – JEA home page)

• Shortest paths in an arrangement with k line orientations.
  D. Eppstein and D. Hart.
  10th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 1999, pp. 310–316.

  We show how to find shortest paths between two points on the lines of an arrangement of n lines with k distinct orientations, in time O(n + k²).

• Incremental and decremental maintenance of planar width.
  D. Eppstein.
  arXiv:cs.CG/9809038.
  10th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 1999, pp. S899-S900.
  J. Algorithms 37 (2): 570–577, 2000.

  We show how to maintain the width of a planar point set, subject to insertions or deletions (but not both) in time O(n^c) per update for any c > 0. The idea is to apply our dynamic closest pair data structure to an appropriate measure of distance between pairs of convex hull features.

  (SODA talk slides)

• Fast approximation of centrality.
  D. Eppstein and J. Wang.
  arXiv:cs.DS/0009005.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 228–229.
  J. Graph Algorithms & Applications 8 (1): 39–45, 2004.

  We use random sampling to quickly estimate, for each vertex in a graph, the average distance to all other vertices.

  (SODA paper)

• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
  D. Eppstein.
  arXiv:cs.DS/0009006.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 329–337.

  Summarizes recent improvements to "3-Coloring in time O(1.3446ⁿ): a no-MIS algorithm". Merged with that paper for the journal version.

  (SODA talk slides – SODA paper)

• Computing the depth of a flat.
  M. Bern and D. Eppstein.
  arXiv:cs.CG/0009024.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 700–701.

  We compute the regression depth of a k-flat in a set of n d-dimensional points, in time O(n^d-2), an order of magnitude faster than the best known algorithms for computing the depth of a point or of a hyperplane. The results from this conference paper have been merged into the full version of "Multivariate Regression Depth".

  (SODA talk slides – SODA paper)

• Internet packet filter management and rectangle geometry.
  D. Eppstein and S. Muthukrishnan.
  arXiv:cs.CG/0010018.
  12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 827–835.

  Rule sets for internet routers and firewalls can be represented as sets of prioritized rectangles; the rule to use for a packet is the maximum priority rectangle containing its (source,destination) address pair. We develop efficient data structures for performing these queries, and find an O(n^3/2) time algorithm for testing whether a rule set contains any ambiguities.

  (SODA paper)

• Möbius-invariant natural neighbor interpolation.
  M. Bern and D. Eppstein.
  arXiv:cs.CG/0207081.
  14th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 2003, pp. 128–129.

  Natural neighbor interpolation is a well-known technique for fitting a surface to scattered data, with some nice properties including smoothness everywhere except the data and exact fitting of linear functions. The interpolated surface is formed from a weighted combination of data values at the "natural neighbors" (neighbors in the Delaunay triangulation), with weights related to Voronoi cell areas. We describe a variation of natural neighbor interpolation, using different weights based on Delaunay circle angles, that remains invariant when the data is transformed by Möbius transformations, and reconstructs harmonic functions in the limit of dense data on a circle.

  (SODA talk slides)

• Dynamic generators of topologically embedded graphs.
  D. Eppstein.
  arXiv:cs.DS/0207082.
  14th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 2003, pp. 599–608.

  We describe a decomposition of graphs embedded on 2-dimensional manifolds into three subgraphs: a spanning tree, a dual spanning tree, and a set of leftover edges with cardinality determined by the genus of the manifold. This tree-cotree decomposition allows us to find efficient data structures for dynamic graphs (allowing updates that change the surface), better constants in bounded-genus graph separators, and efficient algorithms for tree-decomposition of bounded-genus bounded-diameter graphs.

  (SODA talk slides)

• Quasiconvex analysis of backtracking algorithms.
  D. Eppstein.
  arXiv:cs.DS/0304018.
  15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 781–790.
  ACM Trans. Algorithms 2 (4): 492–509 (special issue for SODA 2004), 2006.

  We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.

  The journal version uses the longer title "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms".

  (SODA talk slides)

• Testing bipartiteness of geometric intersection graphs.
  D. Eppstein.
  arXiv:cs.CG/0307023.
  15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 853–861.
  ACM Trans. Algorithms 5(2):15, 2009.

  We consider problems of partitioning sets of geometric objects into two subsets, such that no two objects within the same subset intersect each other. Typically, such problems can be solved in quadratic time by constructing the intersection graph and then applying a graph bipartiteness testing algorithm; we achieve subquadratic times for general objects, and O(n log n) times for balls in R^d or simple polygons in the plane, by using geometric data structures, separator based divide and conquer, and plane sweep techniques, respectively. We also contrast the complexity of bipartiteness testing with that of connectivity testing, and provide evidence that for some classes of object, connectivity is strictly harder due to a computational equivalence with Euclidean minimum spanning trees.

  (SODA talk slides)

• All maximal independent sets and dynamic dominance for sparse graphs.
  D. Eppstein.
  arXiv:cs.DS/0407036.
  16th ACM-SIAM Symp. Discrete Algorithms, Vancouver, 2005, pp. 451–459.
  ACM Trans. Algorithms 5(4):A38, 2009.

  We show how to apply reverse search to list all maximal independent sets in bounded-degree graphs in constant time per set, in graphs from minor closed families in linear time per set, and in sparse graphs in subquadratic time per set. The latter two results rely on new data structures for maintaining a dynamic vertex set in a graph and quickly testing whether the set dominates all other vertices.

  (SODA05 talk slides)

• Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition.
  D. Eppstein.
  arXiv:cs.CG/0604034.
  18th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2007, pp. 29–38.
  ACM Trans. Algorithms 5(3): Article 29, 2009.

  We find efficient constant factor approximation algorithms for hierarchically clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the hyperbolic or Euclidean planes, minimizing the sum of cluster perimeters. Our algorithms for the hyperbolic and Euclidean planes can also be used to provide a pants decomposition with approximately minimum total length.

  (Slides)

• Recognizing partial cubes in quadratic time.
  D. Eppstein.
  arXiv:0705.1025.
  19th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 2008, pp. 1258–1266.
  J. Graph Algorithms and Applications 15 (2): 269–293, 2011.

  We show how to test whether a graph is a partial cube, and if so embed it isometrically into a hypercube, in time O(n²), improving previous O(nm)-time solutions; here n is the number of vertices and m is the number of edges. The ideas are to use bit-parallelism to speed up previous approaches to the embedding step, and to verify that the resulting embedding is isometric using an all-pairs shortest path algorithm from "algorithms for media".

  (slides)

• Self-overlapping curves revisited.
  D. Eppstein and E. Mumford.
  arXiv:0806.1724.
  20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 160–169.
  

  We consider problems of determining when a curve in the plane is the projection of a 3d surface with no vertical tangents. Several problems of this type are NP-complete, but can be solved in polynomial time if a casing of the curve is also given.

  (Elena's SODA talk slides)

• Linear-time algorithms for geometric graphs with sublinearly many crossings.
  D. Eppstein, M. T. Goodrich, and D. Strash.
  arXiv:0812.0893.
  20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 150–159.
  SIAM J. Computing 39 (8): 3814–3829, 2010.

  If a connected graph corresponds to a set of points and line segments in the plane, in such a way that the number of crossing pairs of line segments is sublinear in the size of the graph by an iterated-log factor, then we can find the arrangement of the segments in linear time. It was previously known how to find the arrangement in linear time when the number of crossings is superlinear by an iterated-log factor, so the only remaining open case is when the number of crossings is close to the size of the graph.

• Paired approximation problems and incompatible inapproximabilities.
  D. Eppstein.
  arXiv:0909.1870.
  21st ACM-SIAM Symp. Discrete Algorithms, Austin, Texas, 2010, pp. 1076–1086.

  Considers situations in which two hard approximation problems are presented by means of a single input. In many cases it is possible to guarantee that one or the other problem can be approximated to within a better approximation ratio than is possible for approximating it as a single problem. For instance, it is possible to find either a (1+ε)-approximation to a 1-2 TSP defined from a graph or a n^ε-approximation to the maximum independent set of the same graph, despite lower bounds showing nonexistence of approximation schemes for 1-2 TSP and nonexistence of approximations better than n^1 − ε for independent set. However, for some other pairs of problems, such as hitting set and set cover, we show that solving the paired problem approximately is no easier than solving either problem independently.

  (Slides)

• Windows into relational events: data structures for contiguous subsequences of edges.
  M. J. Bannister, C. DuBois, D. Eppstein, and P. Smyth.
  NIPS 2012 Workshop on Algorithmic and Statistical Approaches for Large Social Networks, South Lake Tahoe, California, 2012 (poster and invited talk).
  24th ACM-SIAM Symp. Discrete Algorithms, New Orleans, Louisiana, 2013, pp. 856–864.
  arXiv:1209.5791.

  We study relational event data in which a collection of actors in a social network have a sequence of pairwise interactions. Contiguous subsequences of these interactions form graphs, and we develop efficient data structures for querying the parameters of these graphs.

• Minimum forcing sets for Miura folding patterns.
  B. Ballinger, M. Damian, D. Eppstein, R. Flatland, J. Ginepro, and T. Hull.
  arXiv:1410.2231.
  26th ACM-SIAM Symp. on Discrete Algorithms, San Diego, 2015, pp. 136–147.

  A forcing set for an origami crease pattern is a subset of the folds with the property that, if these folds are folded the correct way (mountain vs valley) the rest of the pattern also has to be folded the correct way. We use a combinatorial equivalence with three-colored grids to construct minimum-cardinality forcing sets for the Miura-ori folding pattern and for other patterns with differing folds along the same line segments.

  (Slides)

• Treetopes and their graphs.
  D. Eppstein.
  arXiv:1510.03152.
  27th ACM-SIAM Symp. on Discrete Algorithms, Arlington, 2016, pp. 969–984.
  Discrete Comput. Geom. 64 (2), 259–289, 2020 (special issue for Branko Grünbaum).
  

  We describe a class of polytopes of varying dimensions, whose restriction to three dimensions is the class of roofless polyhedra (Halin graphs). We call these polytopes treetopes. We show that the four-dimensional treetopes are closely related to clustered planar graph drawings, and we use this connection to recognize the graphs of four-dimensional treetopes in polynomial time.

  (Slides)

• Finding maximal sets of laminar 3-separators in planar graphs in linear time.
  D. Eppstein and B. Reed.
  arXiv:1810.07825.
  30th ACM-SIAM Symp. on Discrete Algorithms, San Diego, 2019, pp. 589–605.
  

  Given a 3-vertex-connected planar graph, we find a hierarchical decomposition of the graph by 3-vertex separators, such that each piece of the decomposition is 4-vertex-connected, in linear time. The result has applications to an algorithm of Kawarabayashi, Li, and Reed for finding disjoint paths in nonplanar graphs.

  (Slides)