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.