Wolfgang Mulzer and Günter Rote:
Minimum-weight triangulation is NP-hard
- In: Proceedings of the 22nd Annual Symposium on
Computational Geometry, Sedona, June 5–7, 2006. Association
for Computing Machinery, 2006, pp. 1–10. doi:10.1145/1137856.1137859
- Technical report B-05-23-revised, February 2008,
45 pages, arXiv:cs/0601002
[cs.CG], complete version with extra appendices.
- Journal of the ACM 55, no. 2 (May
2008), Article 11, 29 pp.
doi:10.1145/1346330.1346336
Abstract
A triangulation of a planar point set is a maximal plane straight-line
graph whose vertex set is the given set. In the minimum-weight
triangulation (MWT) problem, we are looking for a triangulation of
a
given point set that minimizes the sum of the edge lengths. We prove
that
the decision version of this problem is NP-hard. We use a reduction
from
PLANAR 1-IN-3-SAT. The correct working of the gadgets is established
with
computer assistance, using dynamic programming on polygonal faces, as
well as
the β-skeleton heuristic to certify that certain
edges
belong to the minimum-weight triangulation.
Here are the Python
programs and data for these calculations.
Note on priority
NP-hardness of the POSITIVE PLANAR 1-IN-3-SAT problem has apparently
been shown already by
P. Laroche, Planar 1-in-3 satisfiability is NP-complete, ASMICS Workshop on
Tilings, Deuxièmes journées polyominos et pavages, Ecole Normale Supérieure de
Lyon, 1992, according to a reference in C. Moore and J. M. Robson, Hard tiling problems with simple tiles,
Discrete & Computational Geometry 26 (2001), 573–590,
doi:10.1007/s00454-001-0047-6.
Last update: April 11, 2011.