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.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: August 27, 2003.