A polynomial-time approximation scheme for minimum weight triangulation (PTAS for MWT)

The minimum weight triangulation (MWT) problem — given $n$ points in the plane, find the triangulation minimizing the total Euclidean length of its edges — is NP-hard. The best known polynomial-time approximation is a randomized 14-approximation (in expectation; 21 in the worst case) obtained by Raghvendra and Wessels with a grid-based algorithm, while the only known $(1+\varepsilon)$ -approximation scheme runs in quasi-polynomial time $n^{O(\log^8 n)}$ (Remy and Steger). Whether MWT admits a polynomial-time approximation scheme (PTAS) — for every fixed $\varepsilon>0$ , a polynomial-time algorithm returning a $(1+\varepsilon)$ -approximate triangulation — is posed as an open problem by Raghvendra and Wessels (SODA 2018). No PTAS and no hardness-of-approximation result for MWT appears in the literature.

Background

A triangulation of a planar point set $P$ is a maximal set of pairwise non-crossing straight-line segments with endpoints in $P$ ; equivalently, it decomposes the convex hull of $P$ into triangles whose vertex set is exactly $P$ . The minimum weight triangulation (MWT) problem asks for the triangulation minimizing the total Euclidean length of its edges. The problem has been studied for more than four decades and was a famous open question until Mulzer and Rote proved it NP-hard via a reduction from Planar 1-in-3-SAT (the planar restriction of exact-one-of-three satisfiability, in which exactly one literal per clause must be true; SoCG 2006; Journal of the ACM, 2008); no hardness of approximation beyond NP-hardness — in particular no APX-hardness — appears in the literature surveyed.

A polynomial-time approximation scheme (PTAS) for a minimization problem is an algorithm that, for every fixed $\varepsilon>0$ , runs in time polynomial in the input size $n$ (any dependence on $\varepsilon$ is allowed) and outputs a solution of weight at most $(1+\varepsilon)$ times the optimum. Arora's shifted-quadtree dissection with portals — a randomly shifted recursive grid subdivision of the plane in which the solution is restricted to cross cell boundaries only at a small set of prescribed crossing points, called portals — and independently Mitchell's approach, yielded PTASs for the Euclidean traveling salesman problem (TSP) and many other geometric optimization problems, but, as Arora himself noted, MWT resists this approach: a triangulation is a planar structure whose edges interact globally — moving one edge forces re-triangulation of a surrounding region — so the local patching and charging arguments that work for tour-type problems do not transfer. The related minimum weight Steiner triangulation (MWST), where auxiliary Steiner points (extra vertices not belonging to the input point set) may be added to the triangulation, has also been studied (Eppstein, 1994), but no $(1+\varepsilon)$ -approximation is known for it either.

For MWT itself, the approximation history is: Levcopoulos and Krznaric (1998) showed that a quasi-greedy variant of the greedy triangulation (repeatedly add the shortest edge that does not cross previously added edges) achieves a very large constant approximation ratio; Yousefi and Young (2014) reduced the constant via the linear programming relaxation of a formulation due to Dantzig et al. (1985); Raghvendra and Wessels (SODA 2018) introduced a grid-based algorithm that partitions edges into length levels — shorter edges appear at smaller levels, edges of similar length at the same level — and builds a partial triangulation level by level, first with a variant of the ring heuristic (the classical convex-polygon procedure of repeatedly connecting pairs of adjacent even-numbered vertices) and then with a greedy step, proving an expected approximation ratio of 14 (21 in the worst case) by an Euler-characteristic counting argument (relating vertices, edges, and faces of the partial structure via Euler's formula) against the level-restricted edges of an optimal triangulation. In the conclusion of that paper Raghvendra and Wessels record that it is an open question whether the techniques developed there can be adapted to design a PTAS for MWT, observing that any such construction would maintain finer grids, multiple candidate solutions at each grid level, and dynamic programming to mimic the restricted optimal solution for each grid. The best scheme known remains the quasi-polynomial approximation scheme (QPTAS) of Remy and Steger (STOC 2006; Journal of the ACM, 2009): for every fixed $\varepsilon$ it outputs a $(1+\varepsilon)$ -approximate triangulation, but in $n^{O(\log^8 n)}$ time — quasi-polynomial in $n$ , not polynomial. The open question is exactly the gap between the polynomial-time constant factor of 14 and the quasi-polynomial $(1+\varepsilon)$ scheme. On the practical side, Haas (SoCG 2018) showed that huge MWT instances (up to 30,000,000 points) can be solved to provable optimality with refined LMT-style heuristics (LMT stands for locally minimal triangulation; these techniques discard edges that appear in no triangulation that is stable under single edge flips), but such average-case practical success does not address the worst-case approximation question.

Problem Statement

Does the minimum weight triangulation problem admit a polynomial-time approximation scheme? Construct, for every fixed $\varepsilon>0$ , an algorithm that, given a set $P$ of $n$ points in the plane (not all collinear, so that triangulations exist), runs in time polynomial in $n$ (with arbitrary dependence on $\varepsilon$ ) and outputs a triangulation of $P$ — a maximal set of pairwise non-crossing straight-line segments with endpoints in $P$ , hence with vertex set exactly $P$ and no Steiner points — whose total Euclidean edge length is at most $(1+\varepsilon)\cdot\mathrm{wt}(\mathrm{MWT}(P))$ , where $\mathrm{wt}(\mathrm{MWT}(P))$ is the weight of an optimal minimum weight triangulation of $P$ . A resolution in the negative — for example, a proof that MWT is hard to approximate within some constant factor greater than 1 under an accepted complexity assumption — equally settles the question.

References

Sharath Raghvendra and Mariëtte C. Wessels, 'A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem', Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 101-120, 2018. DOI: 10.1137/1.9781611975031.7, https://arxiv.org/abs/1706.03263 (source of the open question)
Wolfgang Mulzer and Günter Rote, 'Minimum-weight triangulation is NP-hard', Journal of the ACM 55(2), Article 11, pp. 11:1-11:29, 2008. DOI: 10.1145/1346330.1346336, https://doi.org/10.1145/1346330.1346336
Jan Remy and Angelika Steger, 'A quasi-polynomial time approximation scheme for minimum weight triangulation', Journal of the ACM 56(3), Article 15, pp. 15:1-15:47, 2009 (earlier version in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC 2006)). DOI: 10.1145/1516512.1516517, https://doi.org/10.1145/1516512.1516517
Christos Levcopoulos and Drago Krznaric, 'Quasi-Greedy Triangulations Approximating the Minimum Weight Triangulation', Journal of Algorithms 27(2), pp. 303-338, 1998. DOI: 10.1006/jagm.1997.0918, https://doi.org/10.1006/jagm.1997.0918
Arman Yousefi and Neal E. Young, 'On a Linear Program for Minimum-Weight Triangulation', SIAM Journal on Computing 43(1), pp. 25-51, 2014. DOI: 10.1137/120887928, https://doi.org/10.1137/120887928
Sanjeev Arora, 'Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems', Journal of the ACM 45(5), pp. 753-782, 1998. DOI: 10.1145/290179.290180, https://doi.org/10.1145/290179.290180
Andreas Haas, 'Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality', Proceedings of the 34th International Symposium on Computational Geometry (SoCG 2018), Leibniz International Proceedings in Informatics (LIPIcs), volume 99, pp. 44:1-44:14, 2018. DOI: 10.4230/LIPIcs.SoCG.2018.44, https://doi.org/10.4230/LIPIcs.SoCG.2018.44 (preprint arXiv:1802.06415, https://arxiv.org/abs/1802.06415)
David Eppstein, 'Approximating the minimum weight Steiner triangulation', Discrete & Computational Geometry 11(2), pp. 163-191, 1994. DOI: 10.1007/BF02574002, https://doi.org/10.1007/BF02574002
David Eppstein and 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