Günter Rote, Cao An Wang, Lusheng Wang, and Yinfeng Xu:
On constrained minimum pseudotriangulations
to appear in: "Computing and Combinatorics". Proceedings of the 9th
International Computing and Combinatorics Conference (COCOON 2003), Big Sky,
Montana, USA, July 2003. Editors: Tandy Warnow and Binhai Zhu. Lecture Notes
in Computer Science, Springer-Verlag, 2003.
We present three combinatorial bounds: the ratio of the size of
minimum pseudotriangulation of a point set S and the size of minimal
pseudotriangulation contained in a triangulation T of S, the ratio of
the size of the best minimal pseudotriangulation and the worst minimal
pseudotriangulation both contained in a given triangulation T. We also present
a linear-time algorithm for finding a minimal pseudotriangulation contained in
a given triangulation, and we study the minimum pseudotriangulation containing
a given set of non-crossing line segments.
Last update: August 27, 2003.