Abstract
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 pseudotriangulation contained in a triangulation T, the ratio of the size of the best minimal pseudotriangulation and the worst minimal pseudotriangulation both contained in a 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.
| Original language | English |
|---|---|
| Pages (from-to) | 445-454 |
| Number of pages | 10 |
| Journal | Lecture Notes in Computer Science |
| Volume | 2697 |
| DOIs | |
| State | Published - 2003 |