New results on MWT subgraphs

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.