In this paper, we show some properties of a pseudotriangle and present three combinatorial bounds: the ratio of the size of minimum pseudotriangulation of a point set S and the size of minimal pseudotrian-gulation contained in a triangulation T, the ratio of the size of the best minimal pseudotriangulation and the worst minimal pseudotriangulation both contained in given triangulation T, and the maximum number of edges in any settings of S and T. We also present a linear-time algorithm for finding a minimal pseudotriangulation contained in a given triangulation. We finally study the minimum pseudotriangulation containing a given set of non-crossing line segments.
展开▼
