Next: Problem 2: Voronoi Diagram of Moving Points
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.
Perhaps E. L. Lloyd, 1977: [Llo77], cited in Garey and Johnson [GJ79].
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.
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).
triangulations
J. O’Rourke, 31 Jul. 2001; J. O’Rourke, 3 Jan. 2006.
Siu-Wing Cheng and Kam-Hing Lee. . 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.