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
In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 238-247,