Triangulations intersect nicely
Oswin Aichholzer, Günter Rote · 1995
We show that there is a matching between the edges of anytwo 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 minimumweight triangulation which can be computed in polynomial time by matching and network #ow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation. 1 Introduction The aim of this paper is to prove and discuss some surprising and rather general intersection properties of planar triangulations. Given two triangulations of a point set, we can #nd a matching between their edge sets such that matched edges either cross or coincide. This theorem and a few related statements will be proved in Section 2. T...