David Eppstein - Publications

Canadian Conf. Computational Geometry (CCCG)

• Ununfoldable polyhedra.
  M. Bern, E. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Snoeyink.
  arXiv:cs.CG/9908003.
  Tech. rep. CS-99-04, Univ. of Waterloo, Dept. of Computer Science, Aug. 1999.
  11th Canad. Conf. Comp. Geom., 1999.
  4th CGC Worksh. Computational Geometry, Johns Hopkins Univ., 1999.
  Comp. Geom. Theory & Applications (special issue for 4th CGC Worksh.) 24 (2): 51–62, 2003.

  We prove the existence of polyhedra in which all faces are convex, but which can not be cut along edges and folded flat.

  Note variations in different versions: the CCCG one was only Bern, Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable polyhedra with triangular faces". The journal version uses the title "Ununfoldable polyhedra with convex faces" and the combined results from both conference versions.

• Hinged dissections of polyominos and polyforms.
  E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.
  arXiv:cs.CG/9907018.
  11th Canad. Conf. Comp. Geom., 1999.
  Computational Geometry: Theory and Applications 31 (3): 237–262, 2005 (special issue for 11th CCCG).

  We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.

• Regular labelings and geometric structures.
  D. Eppstein.
  arXiv:1007.0221.
  Invited to 22nd Canadian Conference on Computational Geometry (CCCG 2010).
  Invited to Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Springer, Lecture Notes in Comp. Sci. 6506, 2010, p. 1.
  

  We survey regular labelings for straight-line embedding of planar graphs on grids, rectangular partitions, and orthogonal polyhedra, and the many similarities between these different types of labeling.

  (CCCG talk 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.

• Set-difference range queries.
  D. Eppstein, M. T. Goodrich, and J. Simons.
  arXiv:1306.3482.
  25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.

  We show how to use invertible Bloom filters as part of range searching data structures that determine the differences between the members of two sets that lie in a given query range.

  (Slides)

• Universal point sets for planar graph drawings with circular arcs.
  P. Angelini, D. Eppstein, F. Frati, M. Kaufmann, S. Lazard, T. Mchedlidze, M. Teillaud, and A. Wolff.
  HAL-Inria open archive oai:hal.inria.fr:hal-00846953.
  25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.
  J. Graph Algorithms and Applications 18 (3): 313–324, 2014.

  For every positive integer n, there exists a set of n points on a parabola, with the property that every n-vertex planar graph can be drawn without crossings with its vertices at these points and with its edges drawn as circular arcs.

  (Slides)

• Folding polyominoes into (poly)cubes.
  O. Aichholzer, M. Biro, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, A. Hesterberg, I. Kostitsyna, and C. Schmidt.
  27th Canadian Conference on Computational Geometry, Kingston, Ontario, Canada, 2015, pp. 101–106.
  arXiv:1712.09317.
  Int. J. Comp. Geom. & Appl. 28 (3): 197–226, 2018.

  We classify the polyominoes that can be folded to form the surface of a cube or polycube, in multiple different folding models that incorporate the type of fold (mountain or valley), the location of a fold (edges of the polycube only, or elsewhere such as along diagonals), and whether the folded polyomino is allowed to pass through the interior of the polycube or must stay on its surface.

• Maximizing the sum of radii of disjoint balls or disks.
  D. Eppstein.
  arXiv:1607.02184.
  Proc. 28th Canadian Conference on Computational Geometry, Vancouver, BC, Canada, 2016, pp. 260–265.
  J. Computational Geometry 8 (1): 316–339, 2017.
  

  We show how to find a system of disjoint balls with given centers, maximizing the sum of radius of the balls. Our algorithm takes cubic time in arbitrary metric spaces and can be sped up to subquadratic time in Euclidean spaces of any bounded dimension.

  (Slides)

• Forbidden configurations in discrete geometry.
  D. Eppstein.
  Paul Erdős Memorial Lecture, 29th Canadian Conference on Computational Geometry, Ottawa, Canada, 2017.
  Invited talk, 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2017.
  Invited talk, 5th International Combinatorics Conference, Melbourne, Australia, 2017.
  Invited talk, Southern California Theory Day, Irvine, California, 2018.
  Cambridge University Press, 2018.

  We survey problems on finite sets of points in the Euclidean plane that are monotone under removal of points and depend only on the order-type of the points, and the subsets of points (forbidden configurations) that prevent a point set from having a given monotone property.

  (CCCG talk slides – CCCG talk video – SCTD talk slides – Updates, errata, and reviews)

• Geometric fingerprint matching via oriented point-set pattern matching.
  D. Eppstein, M. T. Goodrich, J. Jorgensen, and M. Torres.
  arXiv:1808.00561
  Proc. 30th Canadian Conference on Computational Geometry, Winnepeg, Canada, 2018, pp. 98–113.
  

  When matching fingerprints, the data involves planar points each of which has an associated direction. Motivated by this application, we consider point matching problems in which the distance between points combines both their translational distance and the rotation needed to make their directions align. We provide fast and simple approximation schemes for matching oriented point sets under the directed Hausdorff distance with different allowed groups of transformations.

• Bipartite and series-parallel graphs without planar Lombardi drawings.
  D. Eppstein.
  arXiv:1906.04401.
  Proc. 31st Canadian Conference on Computational Geometry, Edmonton, Canada, 2019, pp. 17–22.
  J. Graph Algorithms & Applications 25 (1): 549–562, 2021.

  Not every bipartite planar graph has a planar Lombardi drawing. Not every plane series parallel graph has a planar Lombardi drawing with the same embedding. The proof involves the properties of cycles of circular-arc-quadrilaterals all sharing the same two vertices, with equal and sharp vertex angles.

  (Slides)

• Some polycubes have no edge-unzipping.
  E. Demaine, M. Demaine, D. Eppstein, and J. O'Rourke.
  arXiv:1907.08433.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 101–105.
  Geombinatorics 31 (3): 101–109, 2022.
  

  We find polycubes that cannot be cut along a simple path through their vertices and edges and unfolded to form a flat polygon in the plane.

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

• Acutely triangulated, stacked, and very ununfoldable polyhedra.
  E. Demaine, M. Demaine, and D. Eppstein.
  arXiv:2007.14525.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 106–113.

  We construct non-convex but topologically spherical polyhedra in which all faces are acute triangles, with no unfolded net.

• New results in sona drawing: hardness and TSP separation.
  M.-W. Chiu, E. Demaine, M. Demaine, D. Eppstein, R. Hearn, A. Hesterberg, M. Korman, I. Parada, and M. Rudoy.
  arXiv:2007.15784.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 63–72.

  A sona drawing is a self-crossing curve in the plane that separates each of a given system of points into its own region. We show that it is hard to find the shortest such curve, and we explore how much shorter than the TSP it can be.

• Angles of arc-polygons and Lombardi drawings of cacti.
  D. Eppstein, D. Frishberg, and M. Osegueda.
  arXiv:2107.03615.
  Proc. 33rd Canadian Conference on Computational Geometry, 2021, pp. 56–64.
  Comp. Geom. Theory & Applications 112: 101982, 2023 (special issue for CCCG 2021).
  

  We precisely characterize the triples vertex angles that are possible for arc-triangles (curved triangles made from circular arcs), and prove an existence theorem for a large class of sets of angles for arc-polygons. Our characterization allows us to prove that every cactus graph has a planar Lombardi drawing for its natural planar embedding (the embedding in which each cycle is a bounded face), but that there exist other embeddings of cacti that have no Lombardi drawing.

• Orthogonal dissection into few rectangles.
  D. Eppstein.
  arXiv:2206.10675.
  34th Canadian Conference on Computational Geometry, 2022, pp. 143–150.
  Discrete Comput. Geom. 73 (1): 129–148, 2025.
  

  The rank of the Dehn invariant of an orthogonal polygon equals the minimum number of rectangles into which it can be transformed by axis-parallel cuts, translation, and gluing. This allows the minimum number of rectangles to be calculated in polynomial time.

  (Slides)

• Reflections in an octagonal mirror maze.
  D. Eppstein.
  arXiv:2206.11413.
  34th Canadian Conference on Computational Geometry, 2022, pp. 129–134.
  

  For two-dimensional scenes consisting of mirrors and opaque walls that are either axis-parallel or with slope ±1, with integer endpoints, it is possible to determine the eventual destination of rational light rays in time polynomial in the description complexity of the scene, even though the number of reflections before a ray reaches this destination may be exponential. The solution involves transforming the problem into one involving interval exchange transformations and from there into another problem involving normal curves on topological surfaces.

  (Slides)

• Locked and unlocked smooth embeddings of surfaces.
  D. Eppstein.
  arXiv:2206.12989.
  34th Canadian Conference on Computational Geometry, 2022, pp. 135–142.
  Computing in Geometry and Topology 2 (2): 5.1–5.20, 2023.

  If a subset of the plane has a continuous shrinking motion of itself, then every smooth isometric embedding of that subset into 3d can be smoothly flattened. However, there exist subsets of the plane with holes, for which some smooth embeddings that are topologically equivalent to a flat embedding cannot be smoothly flattened.

  (Slides)

• On the complexity of embedding in graph products.
  T. Biedl, D. Eppstein, and T. Ueckerdt.
  arXiv:2303.17028.
  Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 77–88.
  Computing in Geometry and Topology 4 (2): 5:1–5:18, 2025.

  Row treewidth (embedding a graph as a subgraph of a strong product of a path with a low treewidth graph), row pathwidth, and row tree-depth are all NP-hard.

• A parameterized algorithm for flat folding.
  D. Eppstein.
  arXiv:2306.11939.
  Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 35–42.
  

  Testing whether an origami folding pattern can be folded flat is fixed-parameter tractable when parameterized by two parameters: the ply (maximum number of layers) of the folding, and the treewidth of a planar graph describing the arrangement of polygons in the flat-folded result. The dependence on treewidth is optimal under the exponential-time hypothesis.

  Merged into "Computational complexities of folding" for journal submission.

• Geometric graphs with unbounded flip-width.
  D. Eppstein and R. McCarty.
  arXiv:2306.12611.
  Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 197–208.

  We show that many constructions for dense geometric graphs produce graphs of unbounded flip-width, frustrating the search for natural classes of graphs that have bounded flip-width but unbounded twin-width.

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

• Well-separated multiagent path traversal.
  G. Dilman, D. Eppstein, V. Polishchuk, and C. Schmidt.
  Proc. 36th Canadian Conference on Computational Geometry, 2024, pp. 137–144.

  We find algorithms and lower bounds for scheduling a sequence of release times for robots to follow the same path as each other, traversing the path at uniform speeds, and not colliding.

• Decremental greedy polygons and polyhedra without sharp angles.
  D. Eppstein.
  arXiv:2507.04538.
  Proc. 37th Canadian Conference on Computational Geometry, 2025, pp. 85–91.
  

  For given elements and a quality function of an element in a subset, monotonically non-increasing with respect to removals of other elements, we can find the max-min-quality subset by a decremental greedy algorithm that repeatedly removes low-quality subsets. We apply this method to find the max-min-angle polygon for points in the plane, the max-min-weight cycle in a directed graph, and several generalizations of both problems.

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