New results on MWT subgraphs

Citation
O. Aicholzer et al., New results on MWT subgraphs, INF PROCESS, 69(5), 1999, pp. 215-219
Citations number
13
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
69
Issue
5
Year of publication
1999
Pages
215 - 219
Database
ISI
SICI code
0020-0190(19990312)69:5<215:NROMS>2.0.ZU;2-D
Abstract
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.