1. Computing pseudotriangulations via branched coverings
- Author
-
Habert, Luc and Pocchiola, Michel
- Subjects
Computer Science - Computational Geometry ,Mathematics - Combinatorics ,52C30, 52A10, 52C40, 68-04, 68U05, 68R05 - Abstract
We describe an efficient algorithm to compute a pseudotriangulation of a finite planar family of pairwise disjoint convex bodies presented by its chirotope. The design of the algorithm relies on a deepening of the theory of visibility complexes and on the extension of that theory to the setting of branched coverings. The problem of computing a pseudotriangulation that contains a given set of bitangent line segments is also examined., Comment: 66 pages, 39 figures
- Published
- 2011
- Full Text
- View/download PDF