**Next:** Problem 2: Voronoi Diagram of Moving Points

- Statement
Can a minimum weight triangulation of a planar point set be found in polynomial time? The

*weight*of a triangulation is its total edge length.- Origin
Perhaps E. L. Lloyd, 1977: [Llo77], cited in Garey and Johnson [GJ79].

- Status/Conjectures
Just solved by Wolfgang Mulzer and Günter Rote, January 2006! http://arxiv.org/abs/cs.CG/0601002. 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).

- Appearances
- Categories
triangulations

- Entry Revision History
J. O’Rourke, 31 Jul. 2001; J. O’Rourke, 3 Jan. 2006.

- [CL98]
Siu-Wing Cheng and Kam-Hing Lee. . In

*ISAAC: 9th Internat. Sympos. Algorithms Computation*, pages 367–376, 1998.- [DMM95]
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.- [Epp94]
D. Eppstein. Approximating the minimum weight Steiner triangulation.

*Discrete Comput. Geom.*, 11:163–191, 1994.- [GJ79]
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.- [Llo77]
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.- [LK96]
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.- [MO01]
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.