New results on MWT subgraphs
O. Aichholzer, F. Aurenhammer, and R. Hainz
be a polygon in the plane. We disprove the conjecture that the
so-called LMT-skeleton coincides with the intersection of all locally minimal
, even for convex polygons
. We introduce an
improved LMT-skeleton algorithm which, for any simple polygon
, and thus a larger subgraph of the minimum-weight
. The algorithm achieves the same in the general point
set case provided the connectedness of the improved LMT-skeleton, which is
given in allmost all practical instances. We further observe that the
is a subset of
for all values
is convex or near-convex. This gives
evidence for the tightness of this bound in the general point set case.
Reference: O. Aichholzer, F. Aurenhammer, and R. Hainz.
New results on MWT subgraphs.
Information Processing Letters, 69:215-219, 1999.
[SFB Report F003-140, TU Graz, Austria, 1998].