8 papers
Minimum-Weight Steiner Triangulation of Convex Polygons Requires Interior Steiner Points
David Eppstein, Zahra Hadizadeh
We construct a convex polygon for which the minimum-weight Steiner triangulation requires an interior Steiner point. This provides a counterexample to a 1994 conjecture of Eppstein…
Tangent Spheres and Integer Distances
David Eppstein
The ErdÅs-Anning theorem states that any point set for which all distances are integers, in a Euclidean space of any dimension, must be either finite or collinear. We prove the sa…
Hamiltonian Cycles in Subdivided Doubles
David Eppstein
The subdivided double construction on 4-regular graphs was used by Potočnik and Wilson to explore semi-symmetric (edge-transitive but not vertex-transitive) graphs, and can be used…
Better Late than Never: the Complexity of Arrangements of Polyhedra
Boris Aronov, Sang Won Bae, Sergio Cabello +4
Let be the subdivision of induced by convex polyhedra having facets in total. We prove that has combinatorial complexity $O(m^{\l…
String Graph Obstacles of High Girth and of Bounded Degree
Maria Chudnovsky, David Eppstein, David Fischer
A string graph is the intersection graph of curves in the plane. KratochvÃl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for…
Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness
David Eppstein, Michael T. Goodrich, Abraham M. Illickan +1
We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a meas…