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.

PostScript file (gzipped) pdf file

other papers about this subject

Last update: January 19, 2018.