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


Problem 1: Minimum Weight Triangulation

Statement
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.
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
[MO01]
Categories
triangulations
Entry Revision History
J. O'Rourke, 31 Jul. 2001; J. O'Rourke, 3 Jan. 2006.

Bibliography

CL98
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.

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.



The Open Problems Project - December 08, 2012