5 papers · 1 filter
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…
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…
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…
Visualizing Treewidth
Alvin Chiu, Thomas Depian, David Eppstein +2
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly sho…