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.
Abstract
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.