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