Computing pseudotriangulations via branched coverings

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.

66 pages, 39 figures

References in corpus (1)

• Multitriangulations, pseudotriangulations and primitive sorting networks

Cited by in corpus (1)

• LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies