Publications with Zahra Hadizadeh
Minimum-weight Steiner triangulation of convex polygons
requires interior Steiner points.
D. Eppstein and
Z. Hadizadeh.
arXiv:2606.25302.
Proc. 38th Canadian Conference on Computational Geometry, 2026,
to appear.
In "Approximating the minimum weight Steiner triangulation" I conjectured that the minimum weight Steiner triangulation of a convex polygon only needs its Steiner points to be on the boundary of the polygon. This would give the triangulation a tree-like structure that could potentially lead to an efficient dynamic programming algorithm for constructing it. Unfortunately, the conjecture is not true: we construct a counterexample.