Complexity of minimum-weight Steiner triangulation of convex polygons: NP-hard or polynomial-time?

For a convex polygon with rational vertex coordinates, the minimum-weight Steiner triangulation problem (MWST) asks for a triangulation of the polygon, allowing additional vertices (Steiner points) placed anywhere in the closed polygon, that minimizes the total Euclidean length of all triangulation edges. Eppstein and Hadizadeh (2026), after constructing the first convex polygon whose optimal Steiner triangulation provably requires an interior Steiner point — refuting a 1994 conjecture of Eppstein that boundary Steiner points always suffice — explicitly pose the open question: is computing the minimum-weight Steiner triangulation of a convex polygon NP-hard, or solvable in polynomial time? No exact algorithm and no hardness result is known for any Steiner triangulation problem — the adjacent literature comprises the NP-hardness of non-Steiner minimum-weight triangulation of point sets, the polynomial dynamic program for non-Steiner polygon triangulation, and approximation-only results for all Steiner variants — so the question is open.

Background

A triangulation of a polygon $P$ is a decomposition of $P$ into triangles whose vertex set includes all vertices of $P$; its weight is the sum of the Euclidean lengths of its edges, each edge counted once (boundary edges and interior diagonals). The minimum-weight triangulation (MWT) problem asks for a triangulation of minimum weight, a classical objective both in combinatorial geometry and in finite-element mesh generation, where total edge length is a proxy for mesh quality. MWT without extra vertices has a long complexity history: Garey and Johnson's 1979 book listed MWT of point sets among the problems neither known NP-complete nor known to be solvable in polynomial time, and Mulzer and Rote (2008) finally proved it NP-hard. For simple polygons (without extra vertices), the non-Steiner minimum-weight triangulation is solvable in polynomial time by a classical dynamic program of Klincsek (1980) over intervals of the boundary.

A Steiner point is an additional vertex not present in the input, usable in the triangulation but placeable anywhere (here: anywhere in the closed polygon, interior or boundary). Allowing Steiner points can strictly reduce the achievable weight: Eppstein (1994) showed that for convex polygons, triangulations without Steiner points can be $\Omega(\log n)$ times more expensive than Steiner triangulations, and that no Steiner triangulation problem is known to be exactly solvable in polynomial time. The minimum-weight Steiner triangulation (MWST) problem was introduced by Clarkson (1991), who gave an $O(\log n)$-approximation; Eppstein (1994) gave a constant-factor quadtree approximation for convex polygons (a quadtree is a recursive subdivision of the plane into squares, used here to generate candidate Steiner points). Eppstein (1994) also observed that triangulations of a convex polygon that use Steiner points only on the boundary have a tree-structured weak dual — the dual graph whose nodes are triangles and whose edges join adjacent triangles — and conjectured that optimal MWST solutions for convex polygons never need interior Steiner points, suggesting a polynomial dynamic program over that tree. Cheng and Lee (2002) extended quadtree-based approximations to polygons with holes, and Cheng and Dey (1999) to three dimensions; Traub (2015) studied Steiner reducing sets (sets whose minimum-weight triangulation is improved by adding Steiner points) structurally. All of these are approximations or structural results; none settles exact complexity.

Eppstein and Hadizadeh (2026) refuted the 1994 conjecture by constructing an explicit convex polygon (28 vertices) for which adding a single interior Steiner point yields a strictly cheaper triangulation than every triangulation using only boundary Steiner points. This shuts off the natural dynamic-programming route based on the tree-like weak dual, leaving the complexity of the problem completely open.

Optimal Steiner points in Euclidean Steiner problems can have irrational coordinates, as in the classical Euclidean Steiner tree problem; the decision version of the question therefore compares $\mathrm{OPT}(P)$ against a rational threshold $t$.

Problem Statement

Let $P$ be a convex polygon with rational vertex coordinates, and let $\mathrm{OPT}(P)$ be the minimum, over all triangulations of $P$ whose vertex set consists of the vertices of $P$ together with any finite set of Steiner points placed anywhere in the closed polygon (boundary or interior), of the total Euclidean length of the triangulation edges, each edge counted once. Determine the computational complexity of computing $\mathrm{OPT}(P)$ — equivalently, of the decision problem: given $P$ and a rational threshold $t$, decide whether $\mathrm{OPT}(P) \le t$. Is this problem NP-hard, or is it solvable in polynomial time?

References

1. David Eppstein, Zahra Hadizadeh. Minimum-Weight Steiner Triangulation of Convex Polygons Requires Interior Steiner Points. arXiv:2606.25302 (2026). DOI: 10.48550/arxiv.2606.25302. https://arxiv.org/abs/2606.25302
2. David Eppstein. Approximating the minimum weight Steiner triangulation. Discrete & Computational Geometry 11(2):163–191 (1994). DOI: 10.1007/BF02574002. https://doi.org/10.1007/bf02574002
3. Kenneth L. Clarkson. Approximation Algorithms for Planar Traveling Salesman Tours and Minimum-Length Triangulations. In Proc. 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1991), pp. 17–23. https://dblp.org/rec/conf/soda/Clarkson91.html
4. Wolfgang Mulzer, Günter Rote. Minimum-weight triangulation is NP-hard. Journal of the ACM 55(2):A11:1–A11:29 (2008). DOI: 10.1145/1346330.1346336. https://doi.org/10.1145/1346330.1346336
5. Siu-Wing Cheng, Kam-Hing Lee. Quadtree, ray shooting and approximate minimum weight Steiner triangulation. Computational Geometry 23(2):99–116 (2002). DOI: 10.1016/S0925-7721(02)00078-0. https://doi.org/10.1016/S0925-7721(02)00078-0
6. Siu-Wing Cheng, Tamal K. Dey. Approximate Minimum Weight Steiner Triangulation in Three Dimensions. In Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 205–214. https://dblp.org/rec/conf/soda/ChengD99.html
7. G. T. Klincsek. Minimal Triangulations of Polygonal Domains. Annals of Discrete Mathematics (Combinatorics 79), pp. 121–123 (1980). DOI: 10.1016/S0167-5060(08)70044-X. https://doi.org/10.1016/S0167-5060(08)70044-X
8. Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979). ISBN 0-7167-1044-7. https://dblp.org/rec/books/fm/GareyJ79.html
9. Cynthia M. Traub. Steiner reducing sets of minimum weight triangulations: Structure and topology. Computational Geometry 49:24–36 (2015). DOI: 10.1016/j.comgeo.2015.04.004. https://doi.org/10.1016/j.comgeo.2015.04.004