Computing pseudotriangulations via branched coverings (Q714984): Difference between revisions

It is shown that a pseudotriangulation and the convex hull of a finite pairwise disjoint set of convex bodies in a topological plane is computable in \(O(n \log n)\) time and linear space, provided the set is represented by its chirotope (i.e. for any triplet of convex bodies their position vector is computable in constant time). The method consists of three computation steps: convex hull, cross-section of the visibility complex, and greedy pseudotriangulation. It extends also to some constrained cases where some of the bitangents between convex bodies are required to belong to the pseudotriangulation.