1. Oswin Aichholzer, Franz Aurenhammer, Siu-Wing Cheng, Naoki Katoh, Michael Taschwer, Günter Rote, and Yin-Feng Xu:

Triangulations intersect nicely

Discrete and Computational Geometry 16 (1996), 339-359, (Zbl 857.68110). doi:10.1007/BF02712872

2. Oswin Aichholzer, Franz Aurenhammer, Günter Rote, and Michael Taschwer:

Triangulations intersect nicely

In: Proceedings of the Eleventh Annual Symposium on Computational Geometry, Vancouver, June 5-7, 1995. Association for Computing Machinery, 1995; pp. 220-229. doi:10.1145/220279.220303. This is an extended abstract of a preliminary version of 1.


Given two triangulations of a point set in the plane, there is always a matching between their edge sets which matches each edge in one triangulation with the identical edge or with a crossing edge in the other triangulation. A similar result holds for the triangles (instead of the edges) of a triangulation.  This matching lemma can be formulated in the general setting of independence systems, and it is easy to prove.

As an application, it is possible to compute in polynomial time lower bounds for the minimum weight triangulation by solving an assignment problem or more general network flow problems.  We exhibit an easy-to-recognize class of point sets where the minimum-weight triangulation coincides with the greedy triangulation.  These are the sets for which the "light" edges, which are crossed by no shorter segments, form a triangulation.

 PostScript file (gzippedpdf file   TeX .dvi file (gzipped)
other papers about this subject