## 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.
Note. 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.