## Günter Rote, Cao An Wang, Lusheng Wang, and Yinfeng Xu:

# On constrained minimum pseudotriangulations

In: *"Computing and Combinatorics". Proceedings of the 9th Annual
International Computing and Combinatorics Conference (COCOON 2003)*, Big Sky,
Montana, USA, July 2003. Editors: Tandy Warnow and Binhai Zhu. Lecture Notes
in Computer Science 2697, Springer-Verlag, 2003, pp. 445–454.
doi:10.1007/3-540-45071-8_45
→BibTeX
### Abstract

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: January 19, 2018.