David Eppstein - Publications

Paths and distances in geometric graphs

• Worst-case bounds for subadditive geometric graphs.
  M. Bern and D. Eppstein.
  9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 183–188.

  For many geometric graph problems for points in the unit square, such as minimum spanning trees, matching, and traveling salesmen, the sum of edge lengths is O(sqrt n) and the sum of dth powers of edge lengths is O(log n). We provide a "gap theorem" showing that if these bounds do not hold for a class of graphs, both sums will instead be Omega(n). For traveling salesmen the O(log n) bound is tight but for some other graphs the sum of dth powers of edge lengths is O(1).

  (Preprint of SCG version)

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

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

• The crust and the beta-skeleton: combinatorial curve reconstruction.
  N. Amenta, M. Bern, and D. Eppstein.
  Graphical Models & Image Processing 60/2 (2): 125–135, 1998.

  We consider the problem of "connect the dots": if we have an unknown smooth curve from which sample points have been selected, we would like to find a curve through the sample points that approximates the unknown curve. We show that if the local sample density is sufficiently high, a simple algorithm suffices: form the Delaunay triangulation of the sample points together with their Voronoi vertices, and keep only those Delaunay edges connecting original sample points. There have been many follow-up papers suggesting alternative methods, generalizing the problem to the reconstruction of curves with sharp corners or to curves and surfaces in higher dimensions, etc.

  (Preprint version)

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

• Minimum dilation stars.
  D. Eppstein and K. Wortman.
  arXiv:cs.CG/0412025.
  21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 321–326.
  Comp. Geom. Theory & Applications 37 (1): 27–37, 2007.

  We show how to test the dilation of a star, embedded in a Euclidean space of bounded dimension, in time O(n log n), and how to find the star center that has the minimum dilation for a given set of leaf points in randomized expected time O(n log n). For two-dimensional points, we can find the minimum dilation center, constrained to be one of the input points, in time O(n 2^α(n) log²n). The unconstrained center placement algorithm involves quasiconvex programming, and is used as a subroutine in the constrained center placement algorithm.

  (SoCG05 talk slides)

• Approximate weighted farthest neighbors and minimum dilation stars.
  J. Augustine, D. Eppstein, and K. Wortman.
  arXiv:cs.CG/0602029.
  Proc. 16th Annual International Computing and Combinatorics Conference (COCOON 2010), Nha Trang, Vietnam.
  Springer, Lecture Notes in Comp. Sci. 6196, 2010, pp. 90–99.
  Discrete Mathematics, Algorithms and Applications 2 (4): 553–565, 2010.

  The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space. This leads to fast approximation algorithms for the constrained minimum dilation star problem in any fixed dimension.

• Happy endings for flip graphs.
  D. Eppstein.
  arXiv:cs.CG/0610092.
  23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 92–101.
  J. Computational Geometry 1 (1): 3–28, 2010.

  We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include convex subsets of lattices, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.

• Studying (non-planar) road networks through an algorithmic lens.
  D. Eppstein, and M. T. Goodrich.
  arXiv:0808.3694.
  Proc. 16th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM GIS 2008), Article 16 (best paper award).
  Invited talk at INFORMS 2009, San Diego.

  We examine US road network data and show that, contrary to the assumptions of much past GIS work, these networks are highly nonplanar. We introduce a class of "multiscale dispersed" networks that better fit the data; these networks are defined by a family of disks of varying sizes such that, if a small number of outliers is removed, the remaining disks cover each point of the plane a constant number of times. As we show, these networks have good graph separators, allowing for efficient algorithms for minimum spanning trees, graph Voronoi diagrams, and related problems.

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

• Optimal embedding into star metrics.
  D. Eppstein and K. Wortman.
  arXiv:0905.0283.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada (best paper award).
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 290–301.

  We provide an O(n³ log²n) algorithm for finding a non-distance-decreasing mapping from a given metric into a star metric with as small a dilation as possible. The main idea is to reduce the problem to one of parametric shortest paths in an auxiliary graph. Specifically, we transform the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. We find a new strongly polynomial time algorithm for this problem, and use it to solve the star metric embedding problem.

  (Slides)

• Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets.
  G. Borradaile and D. Eppstein.
  arXiv:1206.2254.
  24th Canadian Conference on Computational Geometry (CCCG 2012), Prince Edward Island, Canada, 2012, pp. 311–316.
  Comp. Geom. Theory & Applications 49: 8–16, 2015 (special issue for CCCG 2012).

  When a planar point set has the property that its Delaunay triangulation has no large angles, we show how to connect it by a plane graph (having linearly many additional Steiner vertices) in which the distances between the original points are approximations to their Euclidean distance, and in which the total graph weight is at most a constant times the minimum spanning tree weight. The time to construct this graph is near-linear, the same as for integer sorting. We use this result to approximate the traveling salesman problem, for these point sets, in the same time bound.

• Crossing patterns in nonplanar road networks.
  D. Eppstein and S. Gupta.
  arXiv:1709.06113.
  Proc. 25th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM SIGSPATIAL 2017), Redondo Beach, California, pp. 40:1–40:9.
  

  We show that, although an individual edge in a road network can have many crossings, real-world road networks have the property that the crossing graph of their edges is sparse. We prove that networks with this property are themselves sparse and have small separators, allowing many fast algorithms to be generalized from planar graphs to these networks.

• On the edge crossings of the greedy spanner.
  D. Eppstein and H. Khodabandeh.
  arXiv:2002.05854.
  Proc. 37th International Symposium on Computational Geometry (SoCG 2021).
  Leibniz International Proceedings in Informatics (LIPIcs) 189, 2021, pp. 33:1–33:17.

  Greedy spanners are graphs formed from sets of geometric points by considering the pairs of points in sorted order by distance and adding an edge whenever a pair cannot be connected by a short path through the previously-added edges. We show that for points in the Euclidean plane, these graphs have linearly many crossings, that the intersection graph of their edges has bounded degeneracy, and that they have separators of square-root size.

• Distributed construction of lightweight spanners for unit ball graphs.
  D. Eppstein and H. Khodabandeh.
  arXiv:2106.15234.
  Brief announcement, 34th ACM Symposium on Parallelism in Algorithms and Architectures, 2022, pp. 57–59.
  Proc. 36th International Symposium on Distributed Computing (DISC 2022).
  Leibniz International Proceedings in Informatics (LIPIcs) 246, 2022, pp. 21:1–21:23.

  Metric spaces of bounded doubling dimension have spanners with bounded degree, weight a bounded multiple of the minimum spanning tree weight, and dilation arbitrarily close to one, that can be found efficiently by a distributed algorithm.

• Maintaining light spanners via minimal updates.
  D. Eppstein and H. Khodabandeh.
  arXiv:2403.03290.
  Proc. 36th Canadian Conference on Computational Geometry, 2024, pp. 1–15.

  We find a way to maintain a spanner of a dynamic point set, a graph approximating its distances to within a \(1+\varepsilon\) factor while maintaining weight proportionate to the minimum spanning tree. Each change to the point set leads to a logarithmic number of changes to the spanner, although update times remain slow.