# New results on minimum-weight triangulations and the LMT skeleton

R. Hainz, O. Aichholzer, and F. Aurenhammer

### Abstract:

Let be a simple polygon in the plane and let be a minimum-weight triangulation of . We prove that the -skeleton of is a subset of for all values > provided is convex or near-convex. This settles the question of tightness of this bound for a special case and gives evidence for its validity in the general point set case.
We further disprove the conjecture that the so-called -skeleton coincides with the intersection of all locally minimal triangulations, , even for convex polygons . We introduce an improved -skeleton algorithm which, for simple polygons , exactly computes , and thus a larger subgraph of . The algorithm achieves the same in the general point set case provided the connectedness of the improved -skeleton, which is given in allmost all practical instances.

Reference: R. Hainz, O. Aichholzer, and F. Aurenhammer. New results on minimum-weight triangulations and the LMT skeleton. In Proc. European Workshop on Computational Geometry CG '97, pages 4-6, Wuerzburg, Germany, 1997.