The Open Problems Project

Next: Problem 2: Voronoi Diagram of Moving Points

Problem 1: Minimum Weight Triangulation

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

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