New results on minimum-weight triangulations and the LMT skeleton
R. Hainz, O. Aichholzer, and F. Aurenhammer
be a simple polygon in the plane and let
be a minimum-weight
. We prove that the
is a subset
for all values
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
We further disprove the conjecture that the so-called
-skeleton coincides with the intersection of all locally minimal
, even for convex polygons
. We introduce an
-skeleton algorithm which, for simple polygons
, and thus a larger subgraph of
. The algorithm
achieves the same in the general point set case provided the connectedness of
-skeleton, which is given in allmost all practical
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.