Wolfgang Mulzer and Günter Rote:

Minimum-weight triangulation is NP-hard

  1. 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
  2. Technical report B-05-23-revised, February 2008, 45 pages, arXiv:cs/0601002 [cs.CG], complete version with extra appendices.
  3. 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.

  PostScript file (gzipped)   pdf file   free PDF @ACM
other papers about this subject

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.