next up previous
Next: Problem 2: Voronoi Diagram Up: The Open Problems Project Previous: Numerical List of All

Problem 1: Minimum Weight Triangulation

Can a mininimum weight triangulation of a planar point set be found in polynomial time? The weight of a triangulation is its total edge length.
Perhaps E. L. Lloyd, 1977: [Llo77], cited in Garey and Johnson [GJ79].
Just solved by Wolfgang Mulzer and Günter Rote, January 2006! Entry to be updated later...

This problem is one of the few from Garey and Johnson [GJ79, p. 288] whose complexity status remains unknown.

Partial and Related Results
The best approximation algorithms achieve a (large) constant times the optimal length [LK96]; good heuristics are known [DMM95]. If Steiner points are allowed, again constant-factor approximations are known [Epp94,CL98], but it is open to decide even if a minimum-weight Steiner triangulation exists (the minimum might be approached only in the limit).
Entry Revision History
J. O'Rourke, 31 Jul. 2001; J. O'Rourke, 3 Jan. 2006.


Siu-Wing Cheng and Kam-Hing Lee.
Quadtree decomposition, Steiner triangulation, and ray shooting.
In ISAAC: 9th Internat. Sympos. Algorithms Computation, pages 367-376, 1998.

Matthew T. Dickerson, Scott A. McElfresh, and Mark H. Montague.
New algorithms and empirical findings on minimum weight triangulation heuristics.
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 238-247, 1995.

D. Eppstein.
Approximating the minimum weight Steiner triangulation.
Discrete Comput. Geom., 11:163-191, 1994.

M. R. Garey and D. S. Johnson.
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman, New York, NY, 1979.

Errol Lynn Lloyd.
On triangulations of a set of points in the plane.
In Proc. 18th Annu. IEEE Sympos. Found. Comput. Sci., pages 228-240, 1977.

Christos Levcopoulos and Drago Krznaric.
Quasi-greedy triangulations approximating the minimum weight triangulation.
In Proc. 7th ACM-SIAM Sympos. Discrete Algorithms, pages 392-401, 1996.

J. S. B. Mitchell and Joseph O'Rourke.
Computational geometry column 42.
Internat. J. Comput. Geom. Appl., 11(5):573-582, 2001.
Also in SIGACT News 32(3):63-72 (2001), Issue 120.

The Open Problems Project - December 08, 2012