David Eppstein – Publications

Journal and book chapter submissions

• Non-Euclidean Erdős–Anning theorems.
  D. Eppstein.
  arXiv:2401.06328.
  41st International Symposium on Computational Geometry (SoCG 2025), Kanazawa, Japan.
  Leibniz International Proceedings in Informatics (LIPIcs) 332, 2025, pp. 46:1–46:15.

  Non-collinear point sets with integer distances must be finite, for strictly convex distance functions on the plane, for two-dimensional complete Riemannian manifolds of bounded genus, and for geodesic distance on convex surfaces in 3d.

  (SoCG talk slides)

• Fast Schulze voting using quickselect.
  A. Arora, D. Eppstein, and R. L. Huynh.
  arXiv:2411.18790.

  We show how to determine the outcome of a Schulze method election, from an input consisting of an \(m\times m\) array of pairwise margins of victory, in time \(O(m^2\log m)\). The algorithm uses random pivoting like that of quickselect.

• Entropy-bounded computational geometry made easier and sensitive to sortedness.
  D. Eppstein, M. T. Goodrich, A. M. Illickan, and C. A. To.
  arXiv:2508.20489.
  Proc. 37th Canadian Conference on Computational Geometry, 2025, pp. 53–61.

  We define a notion of structural entropy of point sets under which a set has low entropy when it can be covered by few disjoint triangles that are either entirely under the hull of the input or presorted, and show that we can find the hull in time sensitive to this entropy. Generalizations of the same technique apply to geometric maxima, lower envelopes, and visibility polygons.

• Visualizing treewidth.
  A. Chiu, T. Depian, D. Eppstein, M. T. Goodrich, and M. Nöllenburg.
  arXiv:2508.19935.
  33rd International Symposium on Graph Drawing and Network Visualization.
  Leibniz International Proceedings in Informatics (LIPIcs) 357, 2025, pp. 17:1–17:20.

  We experiment with metro-map style visualizations of tree decompositions of graphs. Here, the bags of a tree decomposition are visualized as stations on a metro system, and the vertices of a graph are visualized as metro lines passing through certain stations. Within each bag we display a drawing of the induced subgraph of the bag.