David Eppstein - Publications

Dynamic computational geometry

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

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

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

• Dynamic geometric optimization.
  D. Eppstein.
  Invited talk, 3rd MSI Worksh. Computational Geometry, 1993, p. 14.
  
• Computing the discrepancy.
  D. P. Dobkin and D. Eppstein.
  9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 47–52.

  Measures how well a sample of points from a set works as a discrete approximation to the continuous measure of shapes in the set, using algorithms based on Overmars and van Leeuwen's dynamic convex hull data structure. Some versions of the problem also involve subroutines for finding the deepest point in an arrangement of quadrants or orthants.

  This paper was merged with results of Mitchell to form the journal version, "Computing the discrepancy with applications to supersampling patterns".

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

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

• Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions.
  D. Eppstein and J. Erickson.
  14th ACM Symp. Comp. Geom., Minneapolis, 1998, pp. 58–67.
  Disc. Comp. Geom. 22 (4): 569–592, 1999 (special issue for SCG 1998).

  We use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" to detect collisions among a collection of moving objects in sublinear time per collision. As one application, we can construct the straight skeleton of Aichholzer et al (and the mitered offset curves from which it is defined) in subquadratic time.

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

• Graphs for dynamic geometry.
  D. Eppstein.
  Invited talk, Worksh. Dynamic Graph Algorithms, Victoria, Canada, 2000.

  This talk surveys work on computational geometry algorithms that use dynamic graph data structures, and the different kinds of geometric graph arising in this work.

• Lazy algorithms for dynamic closest pair with arbitrary distance measures.
  J. Cardinal and D. Eppstein.
  Tech. Rep. 502, Univ. Libre de Bruxelles, Computer Science Dept., 2003.
  Worksh. Algorithm Engineering and Experiments (ALENEX), New Orleans, 2004, pp. 112–119.

  We modify my previous data structures for dynamic closest pairs, to use a lazy deletion mechanism, and show in experiments that the results are an improvement on the unmodified structures.

• Finding all maximal subsequences with hereditary properties.
  D. Bokal, S. Cabello, and D. Eppstein.
  Proc. 31st Int. Symp. on Computational Geometry, Eindhoven, the Netherlands, June 2015.
  Leibniz International Proceedings in Informatics (LIPIcs) 34, pp. 240–254.

  We study problems in which the input is a sequence of points in the plane and we wish to find, for each position in the sequence, the longest contiguous subsequence that begins at that position and has some geometric property. For many natural properties we can find all such maximal subsequences in linear or near-linear time.

  (Slides)

• Dynamic products of ranks.
  D. Eppstein.
  arXiv:2007.08123.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 199–205.

  We provide data structures for the following problem: maintain a collection of points in the Euclidean plane, subject to insertions or deletions, and after each update find the point whose product of ranks according to the two sorted orders of the points by x- and y-coordinates is as small or as large as possible.