Let P be a polygon in the plane. We disprove the conjecture that the so-cal
led LMT-skeleton coincides with the intersection of all locally minimal tri
angulations, LMT(P), even for convex polygons P. We introduce an improved L
MT-skeleton algorithm which, for any simple polygon P, exactly computes LMT
(P), and thus a larger subgraph of the minimum-weight triangulation MWT(P).
The algorithm achieves the same in the general point set case provided the
connectedness of the improved LMT-skeleton, which is given in almost all p
ractical instances.
We further observe that the beta-skeleton of P is a subset of MWT(P) for al
l values beta > root 4/3 provided P is convex or near-convex. This gives ev
idence for the tightness of this bound in the general point set case. (C) 1
999 Elsevier Science B.V. All rights reserved.