32 citations · 32 across the 10 of their papers we have counts for
6 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 sam…
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…
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…
Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature
David Eppstein, Michael T. Goodrich, Abraham M. Illickan
We study algorithms for drawing planar graphs and 1-planar graphs using cubic Bézier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC draw…