Miscellaneous geometry
Horizon theorems for lines and polygons.
M. Bern, D. Eppstein, P. Plassman, and F. Yao.
Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. Goodman, R. Pollack, and W. Steiger, eds.,
DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6, Amer. Math. Soc., 1991, 45–66.The total complexity of the cells in a line arrangement that are cut by another line is at most \(15n/2\). The complexity of cells cut by a convex \(k\)-gon is \(O(n\alpha(n,k))\). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.
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.
Asymptotic speed-ups in constructive solid geometry.
D. Eppstein.
Tech. Rep. 92-87, ICS, UCI, 1992.
Algorithmica 13: 462–471, 1995.Finds boundary representations of CSG objects. Uses techniques from dynamic graph algorithms, including a tree partitioning technique of Frederickson and a new data structure for maintaining the value of a Boolean expression with changing variables in time O(log n / log log n) per update.
Application Challenges to Computational Geometry.
The Computational Geometry Impact Task Force Report.
Tech. Rep. TR-521-96, Princeton University, April 1996.
Advances in Discrete and Computational Geometry – Proc. 1996 AMS-IMS-SIAM Joint Summer Research Conf. Discrete and Computational Geometry: Ten Years Later, Contemporary Mathematics 223, Amer. Math. Soc., 1999, pp. 407–423.
Emerging challenges in computational topology.
M. Bern, D. Eppstein, et al.
arXiv:cs.CG/9909001.This is the report from the ACM Workshop on Computational Topology run by Marshall and myself in Miami Beach, June 1999. It details goals, current research, and recommendations in this emerging area of collaboration between computer science and mathematics.
Fat 4-polytopes and fatter 3-spheres.
D. Eppstein, G. Kuperberg, and G. Ziegler.
arXiv:math.CO/0204007.
Discrete Geometry: In honor of W. Kuperberg's 60th birthday, Pure and Appl. Math. 253, Marcel Dekker, pp. 239–265, 2003.We introduce the fatness parameter of a 4-dimensional polytope P, (f1+f2)/(f0+f3). It is open whether all 4-polytopes have bounded fatness. We describe a hyperbolic geometry construction that produces 4-polytopes with fatness > 5.048, as well as the first infinite family of 2-simple, 2-simplicial 4-polytopes and an improved lower bound on the average kissing number of finite sphere packings in R3. We show that fatness is not bounded for the more general class of strongly regular CW decompositions of the 3-sphere.
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.
Optimized color gamuts for tiled displays.
M. Bern and D. Eppstein.
arXiv:cs.CG/0212007.
19th ACM Symp. Comp. Geom., San Diego, 2003, pp. 274–281.We consider the problem of finding a large color space that can be generated by all units in multi-projector tiled display systems. Viewing the problem geometrically as one of finding a large parallelepiped within the intersection of multiple parallelepipeds, and using colorimetric principles to define a volume-based objective function for comparing feasible solutions, we develop an algorithm for finding the optimal gamut in time O(n3), where n denotes the number of projectors in the system. We also discuss more efficient quasiconvex programming algorithms for alternative objective functions based on maximizing the quality of the color space extrema.
Möbius transformations in scientific computing.
D. Eppstein.
Talk at SIAM Conf. on Computational Science and Engineering, San Diego, 2003.This talk, for the CSE session on combinatorial scientific computing, surveys my work with Marshall Bern on optimal Möbius transformation and Möbius-invariant natural neighbor transformation.
Guest editor's forward.
D. Eppstein.
Disc. Comp. Geom. 30: 1–2, 2003 (special issue for 17th Symp. Comp. Geom.)
Uninscribable four-regular polyhedron.
M. Dillencourt and D. Eppstein.
Electronic Geometry Models 2003.08.001.We find an example of a three-dimensional polyhedron, with four edges per vertex, that can not be placed in convex position with all vertices on the surface of a sphere.
Guard placement for efficient point-in-polygon proofs.
D. Eppstein, M. T. Goodrich, and N. Sitchinava.
arXiv:cs.CG/0603057.
23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 27–36.The problem is to place as few wedges as possible in the plane such that a desired polygon can be formed as some monotone Boolean combination of the wedges. The motivation is for wireless devices to prove that they are located within a target area by their ability to communicate with a subset of base stations (the wedges). We provide upper and lower bounds on the number of wedges needed for several classes of polygons.
Straight skeletons of three-dimensional polyhedra.
G. Barequet, D. Eppstein, M. T. Goodrich, and A. Vaxman.
arXiv:0805.0022.
Proc. 16th European Symp. Algorithms, Karlsruhe, Germany, 2008.
Springer, Lecture Notes in Comp. Sci. 5193, 2008, pp. 148–160.A straight skeleton is defined by the locus of points crossed by the edges and vertices of a polyhedron as it undergoes a continuous shrinking process in which the faces move inwards at constant speed. We resolve some ambiguities in the definition of these shapes, define efficient algorithms for polyhedra with axis-parallel faces, show that arbitrary polyhedra have strictly more complicated straight skeletons, and report on results from an implementation of our algorithm for arbitrary polyhedra.
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.
Planar Voronoi diagrams for sums of convex functions, smoothed distance and dilation.
M. Dickerson, D. Eppstein, and K. Wortman.
arXiv:0812.0607.
7th Int. Symp. Voronoi Diagrams in Science and Engineering (ISVD 2010), Quebec City, Canada, pp. 13–22.Investigates Voronoi diagrams for a "smoothed distance" in which the distance between two points p and q is inversely weighted by the perimeter of triangle opq for a fixed point o, its relation to dilation of star networks centered at o, and its generalization to minimization diagrams of certain convex functions. When the function to be minimized is suitably well-behaved, its level sets form pseudocircles, the bisectors of the minimization diagram form pseudoline arrangements, and the diagram itself has linear complexity.
Area-universal rectangular layouts.
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
arXiv:0901.3924.
25th Eur. Worksh. Comp. Geom., Brussels, Belgium, 2009.
25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, pp. 267–276.A partition of a rectangle into smaller rectangles is "area-universal" if any vector of areas for the smaller rectangles can be realized by a combinatorially equivalent partition. These partitions may be applied, for instance, to cartograms, stylized maps in which the shapes of countries have been distorted so that their areas represent numeric data about the countries. We characterize area-universal layouts, describe algorithms for finding them, and discuss related problems. The algorithms for constructing area-universal layouts are based on the distributive lattice structure of the set of all layouts of a given dual graph.
Merged with "Orientation-constrained rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".
Animating a continuous family of two-site distance function Voronoi diagrams (and a proof of a complexity bound on the number of non-empty regions).
M. Dickerson and D. Eppstein.
25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, video and multimedia track, pp. 92–93.We investigate distance from a pair of sites defined as the sum of the distances to each site minus a parameter times the distance between the two sites. A given set of n sites defines n(n-1)/2 pairs and n(n-1)/2 distances in this way, from which we can determine a Voronoi diagram. As we show, for a wide range of parameters, the diagram has relatively few regions because the pairs that have nonempty Voronoi regions must be Delaunay edges.
Orientation-constrained rectangular layouts.
D. Eppstein and E. Mumford.
arXiv:0904.4312.
Algorithms and Data Structures Symposium (WADS), Banff, Canada.
Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 266–277.We show how to find a stylized map in which regions have been replaced by rectangles, preserving adjacencies between regions, with constraints on the orientations of adjacencies between regions. For an arbitrary dual graph representing a set of adjacencies, and an arbitrary set of orientation constraints, we can determine whether there exists a rectangular map satisfying those constraints in polynomial time. The algorithm is based on a representation of the set of all layouts for a given dual graph as a distributive lattice, and on Birkhoff's representation theorem for distributive lattices.
Merged with "Area-universal rectangular layouts" to form the journal version, "Area-universal and constrained rectangular layouts".
Graph-theoretic solutions to computational geometry problems.
D. Eppstein.
Invited talk, the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France, 2009.
Springer, Lecture Notes in Comp. Sci. 5911, 2009, pp. 1–16.
arXiv:0908.3916.We survey problems in computational geometry that may be solved by constructing an auxiliary graph from the problem and solving a graph-theoretic problem on the auxiliary graph. The problems considered include the art gallery problem, partitioning into rectangles, minimum diameter clustering, bend minimization in cartogram construction, mesh stripification, optimal angular resolution, and metric embedding.
Curvature-aware fundamental cycles.
P. Diaz-Gutierrez, D. Eppstein, and M. Gopi.
17th Pacific Conf. Computer Graphics and Applications, Jeju, Korea, 2009.
Computer Graphics Forum 28 (7): 2015–2024, 2009.Considers heuristic modifications to the tree-cotree decomposition of my earlier paper Dynamic generators of topologically embedded graphs, to make the set of fundamental cycles found as part of the decomposition follow the contours of a given geometric model.
Going off-road: transversal complexity in road networks.
D. Eppstein, M. T. Goodrich, and L. Trott.
arXiv:0909.2891.
Proc. 17th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems, Seattle, 2009, pp. 23–32.Shows both theoretically and experimentally that the number of times a random line crosses a road network is asymptotically upper bounded by the square root of the number of road segments.
Optimally fast incremental Manhattan plane embedding and planar tight span construction.
D. Eppstein.
arXiv:0909.1866.
J. Computational Geometry 2 (1): 144–182, 2011.Shows that, when the tight span of a finite metric space is homeomorphic to a subset of the plane, it has the geometry of a Manhattan orbifold and can be constructed in time linear in the size of the input distance matrix. As a consequence, it can be tested in the same time whether a metric space is isometric to a subset of the L1 plane.
Hyperconvexity and metric embedding.
D. Eppstein.
Invited talk, Fifth William Rowan Hamilton Geometry and Topology Workshop, Dublin, Ireland, 2009.
Invited talk at IPAM Workshop on Combinatorial Geometry, UCLA, 2009.Surveys hyperconvex metric spaces, tight spans, and my work on Manhattan orbifolds, tight span construction, and optimal embedding into star metrics.
Cloning Voronoi diagrams via retroactive data structures.
M. Dickerson, D. Eppstein, and M. T. Goodrich.
arXiv:1006.1921.
18th Eur. Symp. Algorithms, Liverpool, 2010.
Springer, Lecture Notes in Comp. Sci. 6346, 2010, pp. 362–373.We analyze the security of an online geometric database that allows planar nearest-neighbor queries but that does not wish the entire database to be copied by a competitor. We show that, under several models of how the query answers are returned, the database can be copied in a linear or near-linear number of queries. Our method for the competitor to copy the database is based on simulating Fortune's sweep-line algorithm for Voronoi diagrams, backtracking when the simulation discovers the existence of another point that invalidates earlier parts of the Voronoi diagram construction, and using retroactive data structures to perform the backtracking steps efficiently.
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.
Privacy-preserving data-oblivious geometric algorithms for geographic data.
D. Eppstein, M. T. Goodrich, and R. Tamassia.
Proc. 18th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM GIS 2010), San Jose, California, pp. 13–22.
arXiv:1009.1904.An algorithm is data-oblivious if the memory access patterns it makes depend only on the input size and not on the actual input values; data-oblivious algorithms are an important building block of cryptographic protocols that allow algorithmic tasks to be solved by parties who each have some subset of the input data that they do not wish to reveal. We show how to solve several basic geometric problems data-obliviously, including construction of convex hulls, quadtrees, and well-separated pair decompositions, and computation of closest pairs and all nearest neighbors.
Bounds on the complexity of halfspace intersections when the bounded faces have small dimension.
D. Eppstein and M. Löffler.
Proc. 27th ACM Symp. on Computational Geometry, Paris, 2011, pp. 361–368.
arXiv:1103.2575.
Discrete Comput. Geom. 50 (1): 1–21, 2013.Suppose that P is the intersection of n halfspaces in D dimensions, but that the bounded faces of P are at most d-dimensional, for some d that is much smaller than D. Then in this case we show that the number of vertices of P is O(nd), independent of D. We also investigate related bounds on the number of bounded faces of all dimensions of P, and algorithms for efficiently listing the vertices and bounded faces of P.
On 2-site Voronoi diagrams under geometric distance functions.
G. Barequet, M. Dickerson, D. Eppstein, D. Hodorkovsky, and K. Vyatkina.
27th Eur. Worksh. Comp. Geom., Antoniushaus Morschach, Switzerland, 2011, pp. 59–62.
Proc. 8th Int. Symp. Voronoi Diagrams in Science and Engineering, Qing Dao, China, 2011, pp. 31–38.
arXiv:1105.4130.
J. Computer Science and Technology 28 (2): 267–277, 2013.We study the combinatorial complexity of generalized Voronoi diagrams that determine the closest two point sites to a query point, where the distance from the query point to a pair of sites is a combination of the individual distances to the sites and the distance from one site in the pair to the other.
Adjacency-preserving spatial treemaps.
K. Buchin, D. Eppstein, M. Löffler, M. Nöllenburg, and R. I. Silveira.
arXiv:1105.0398.
12th International Symposium on Algorithms and Data Structures (WADS 2011), New York, 2011.
Springer, Lecture Notes in Comp. Sci. 6844, 2011, pp. 159–170.
J. Computational Geometry 7 (1): 100–122, 2016.We study the recursive partitions of rectangles into sets of rectangles, and partitions of those rectangles into smaller rectangles, to form stylized visualizations of hierarchically subdivided geographic regions. There are several variations of varying difficulty depending on how much of the geographic information from the input we require the output to preserve.
Tracking moving objects with few handovers.
D. Eppstein, M. T. Goodrich, and M. Löffler.
arXiv:1105.0392.
12th International Symposium on Algorithms and Data Structures (WADS 2011), New York, 2011.
Springer, Lecture Notes in Comp. Sci. 6844, 2011, pp. 362–373.We apply competitive analysis to the problem of deciding online which cell phone tower to change to when a phone moves out of the coverage region of the tower it is connected to. We show that, when the coverage regions have constant ply (at most a constant number of them overlap any point of the plane) it is possible to get within a constant factor of the minimum possible number of handovers that an offline algorithm could achieve.
Improved grid map layout by point set matching.
D. Eppstein, M. van Kreveld, B. Speckmann, and F. Staals.
28th European Workshop on Computational Geometry (EuroCG'12), Assisi, Italy, 2012.
6th IEEE Pacific Visualization Conf. (PacificVis), Sydney, Australia, 2013.
Int. J. Comput. Geom. Appl. 25 (2): 101–122, 2015.We study the problem of matching geographic regions to points in a regular grid, minimizing the distance between each region's centroid and the corresponding grid point, and preserving as much as possible the relative orientations between pairs of regions.
Area-universal and constrained rectangular layouts.
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
SIAM J. Computing 41 (3): 537–564, 2012.A combined journal version of "Area-universal rectangular layouts" and "Orientation-constrained rectangular layouts".
UOBPRM: a uniform distributed obstacle-based PRM.
H.-Y. Yeh, S. Thomas, D. Eppstein, and N. Amato.
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2012), Vilamoura, Algarve, Portugal, 2012, pp. 2655–2662.We use a method based on intersecting obstacles with line segments in order to uniformly sample from obstacle surfaces in the probabilistic roadmap method for robot motion planning.
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.
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.
Approximate greedy clustering and distance selection for graph metrics.
D. Eppstein, S. Har-Peled, and A. Sidiropoulos.
arXiv:1507.01555.
J. Computational Geometry 11 (1): 629–652, 2020.We provide fast approximation algorithms for the farthest-first traversal of graph metrics.
Covering many points with a small-area box.
M. De Berg, S. Cabello, O. Cheong, D. Eppstein, and C. Knauer.
arXiv:1612.02149.
J. Computational Geometry 10 (1): 207–222, 2019.We give an efficient algorithm for finding the smallest axis-parallel rectangle covering a given number of points out of a larger set of points in the plane.
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)
Grid peeling and the affine curve-shortening flow.
D. Eppstein, S. Har-Peled, and G. Nivasch.
arXiv:1710.03960.
Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 109–116.
Experimental Mathematics 29 (3): 306–316, 2020.We conjecture, based on experiments, that approximating a convex shape by the set of grid points inside it, for a fine enough grid, and then finding the convex layers of the resulting point set, produces curves that are close to those produced by affine curve-shortening, a continuous process on smooth curves.
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.
The parameterized complexity of finding point sets with hereditary properties.
D. Eppstein and D. Lokshtanov.
arXiv:1808.02162
Proc. 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 2018.
Leibniz International Proceedings in Informatics (LIPIcs) 115, 2018, pp. 11:1–11:14.We exhibit a hereditary property of planar point sets (depending only on the order type of a point set) such that under standard assumptions there is no fixed-parameter-tractable algorithm to find a k-point subset with the property. On the other hand, several natural classes of properties have FPT algorithms for this problem, including the properties that are true for all collinear point sets or false for at least one convex polygon.
Counting polygon triangulations is hard.
D. Eppstein.
arXiv:1903.04737.
Proc. 35th Int. Symp. on Computational Geometry, Portland, Oregon, June 2019.
Leibniz International Proceedings in Informatics (LIPIcs) 129, 2019, pp. 33:1–33:17.
Discrete Comput. Geom. 64 (4): 1210–1234, 2020 (special issue for SoCG 2019).Given a polygon with holes, it is #P-complete to determine how many triangulations it has.
Graphs in nature.
D. Eppstein.
Invited talk at Symposium on Geometry Processing, Milan, Italy, July 2019.
Invited talk at Algorithms and Data Structures Symposium, Edmonton, Canada, August 2019.
Invited talk at International Colloquium on Graph Theory and Combinatorics, Montpellier, France, July 2022.I survey results on characterizing the graphs formed on planar surfaces according to several natural processes: motorcycle graphs, Gilbert tessellations, and the contact graphs of line segments from needle-like crystal growth and crack formation; the graphs of planar soap bubble foams; and graphs representing the fold patterns of crumpled paper.
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.
On polyhedral realization with isosceles triangles.
D. Eppstein.
arXiv:2009.00116.
Graphs and Combinatorics 37 (4): 1247–1269, 2021.We find convex polyhedra with all faces triangular that cannot be realized with all faces isosceles, and new families of convex polyhedra with congruent isosceles-triangle faces.
Geometric dominating sets – A minimum version of the no-three-in-line problem.
O. Aichholzer, D. Eppstein, and E.-M. Hainzl.
37th European Workshop on Computational Geometry (EuroCG 2021), pp. 17:1–17:7.
arXiv:2203.13170.
Comp. Geom. Theory & Applications 108: 101913, 2023 (special issue for EuroCG).We study how few points can be placed in a grid so that all remaining grid points are collinear with two of the placed points.
Multifold tiles of polyominoes and convex lattice polygons.
K. Chida, E. Demaine, M. Demaine, D. Eppstein, A. Hesterberg, T. Horiyama, J. Iacono, H. Ito, S. Langerman, R. Uehara, and Y. Uno.
23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 2021, pp. 28–29.
Thai Journal of Mathematics 21 (4): 957–978, 2023.We investigate shapes whose congruent copies can cover the plane exactly \(k\) times per point, but not a number of times that is a nonzero integer smaller than \(k\). We find polyominoes with this property for all \(k\ge 2\), and convex integer-coordinate polygons with this property for \(k=5\) and for all \(k\ge 7\).
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.
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.
Geodesic paths passing through all faces on a polyhedron.
E. Demaine, M. Demaine, D. Eppstein, H. Ito, Y. Katayama, W. Maruyama, and Y. Uno.
24th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, September 9–11, 2022.
Springer, Lecture Notes in Comp. Sci. 14364 (2026), pp. 184–209.Which convex polyhedra have the property that there exist two points on the surface of the polyhedron whose shortest path passes through all of the faces of the polyhedron? The answer is yes for the tetrahedron, and for certain prisms, but no for all other regular polyhedra.
Non-crossing Hamiltonian paths and cycles in output-polynomial time.
D. Eppstein.
arXiv:2303.00147.
Proc. 39th International Symposium on Computational Geometry (SoCG 2023).
Leibniz International Proceedings in Informatics (LIPIcs) 258, 2023, pp. 29:1–29:16.
Algorithmica 86: 3027–3053, 2024.For any point set, the numbers of non-crossing paths, non-crossing Hamiltonian paths, non-crossing surrounding polygons, and non-crossing Hamiltonian cycles can be bounded above and below by functions of two simple parameters: the minimum number of points whose deletion leaves a collinear subset, and the number of points interior to the convex hull. Because their bounds have the same form, the numbers of the two types of paths are bounded by polynomials of each other, as are the numbers of the two types of polygons. We use these relations to list non-crossing Hamiltonian paths and polygonalizations in time polynomial in the number of outputs.
Widths of geometric graphs.
D. Eppstein.
Invited talk, Workshop on Parameterized Algorithms for Geometric Problems, CG Week 2023.Many computational geometry problems can be solved by transforming them into a graph problem on a geometric graph. When the graph has low width, for some form of graph width, this can often lead to efficient classical or parameterized algorithms. We survey the geometric graphs that always have low width, the geometric graphs that can have high width, and the opportunities for parameterization obtained by studying low-width instances of graphs that sometimes have high width.
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.
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.
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.
Noncrossing longest paths and cycles.
G. Aloupis, A. Biniaz, P. Bose, J.-L. De Carufel, D. Eppstein, A. Maheshwari, S. Odak, M. Smid, C. Tóth, and P. Valtr.
32nd International Symposium on Graph Drawing and Network Visualization.
Leibniz International Proceedings in Informatics (LIPIcs) 320, 2024, pp. 36:1–36:17.
arXiv:2410.05580.
Graphs and Combinatorics 41, article 122 (25pp), 2025.The shortest path or cycle through given planar points (the solution to the traveling salesperson problem) never crosses itself: any crossing can be eliminated by a local move that shortens the tour. One might think that, correspondingly, the longest path or cycle through enough planar points always crosses itself. We show that this is not the case: there exist arbitrarily large point sets for which the longest path or cycle has no crossing.
Computational geometry with probabilistically noisy primitive operations.
D. Eppstein, M. T. Goodrich, and V. Sridhar.
arXiv:2501.07707.
Proc. 19th Algorithms and Data Structures Symposium (WADS 2025).
Leibniz International Proceedings in Informatics (LIPIcs) 349, 2025, pp. 24:1–24:20.An algorithm that uses Boolean primitive operations, like comparisons, that may be erroneous with some small independent probability per call, may be made to run correctly with high probability by repeating each primitive enough times to be sure its majority result is correct, but this incurs a logarithmic time penalty. Prior work avoids this penalty for sorting; we extend this speedup to algorithms in computational geometry that can be formulated using path search in DAGs. Applications of our "path-guided pushdown random walk" technique include point location, plane sweep, convex hulls, and Delaunay triangulation.
Better late than never: the complexity of arrangements of polyhedra.
B. Aronov, S. W. Bae, O. Cheong, D. Eppstein, C. Knauer, and R. Seidel.
41st European Workshop on Computational Geometry (EuroCG 2025), Liblice, Czech Republic, pp. 62:1–62:4.
arXiv:2506.03960.My 1994 paper "On the number of minimal 1-Steiner trees" with Aronov and Bern, in some preliminary manuscript versions, included a bound of \(O(m^{\lceil d/2\rceil}n^{\lfloor d/2\rfloor})\) on the complexity of an arrangement of \(m\) convex polytopes given as intersections of a total of \(n\) halfspaces, interpolating between the upper bound theorem for polytopes and the complexity of hyperplane arrangements. However, the manuscript and the proof were lost. This paper re-proves the result, with better care for the degenerate cases.
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.
Bicriteria polygon aggregation with arbitrary shapes.
L. Blank, D. Eppstein, J.-H. Haunert, H. Haverkort, B. Kolbe, P. Mayer, P. Mutzel, A. Naumann, and J. Sauer.
arXiv:2507.11212.We consider a problem of shape aggregation in which we cluster a collection of disjoint regions in the plane by finding a collection of surrounding shapes, covering all the given regions and minimizing a linear combination of area and perimeter. The tradeoff between area and perimeter gives us a nested family of clusterings ranging from each given region forming its own cluster to a single cluster for all the regions. The cluster boundaries are straight line segments and circular arcs, leading to a discretization of the clustering problem that allows its optimal solution to be found in polynomial time by a transformation to network flow.