Triangulations intersect nicely
O. Aichholzer, F. Aurenhammer, S.-W. Cheng, N. Katoh, G. Rote,
M. Taschwer, and Y.-F. Xu
We show that there is a matching between the edges of any two triangulations of
a planar point set such that an edge of one triangulation is matched either
to the identical edge in the other triangulation or to an edge that crosses
it. This theorem also holds for the triangles of the triangulations and in
general independence systems. As an application, we give some lower bounds
for the minimum weight triangulation which can be computed in polynomial time
by matching and network flow techniques. We exhibit an easy-to-recognize
class of point sets for which the minimum-weight triangulation coincides with
the greedy triangulation.
Reference: O. Aichholzer, F. Aurenhammer, S.-W. Cheng, N. Katoh, G. Rote,
M. Taschwer, and Y.-F. Xu.
Triangulations intersect nicely.
Discrete & Computational Geometry, 16:339-359, 1996.
Special Issue. [SFB Report F003-030, TU Graz, Austria, 1995].