New results on MWT subgraphs

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

Abstract:

Let $P$ be a polygon in the plane. We disprove the conjecture that the so-called LMT-skeleton coincides with the intersection of all locally minimal triangulations, $LMT(P)$, even for convex polygons $P$. We introduce an improved LMT-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 allmost all practical instances. We further observe that the $\beta$-skeleton of $P$ is a subset of $MWT(P)$ for all values $\beta > \sqrt{\frac{4}{3}}$ provided $P$ 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].