Computing pseudotriangulations via branched coverings
From MaRDI portal
Publication:714984
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Non-Desarguesian affine and projective planes (51A35) Convex sets in (2) dimensions (including convex curves) (52A10) General geometric structures on low-dimensional manifolds (57M50)
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.
Recommendations
- Algorithmic aspects of branched coverings
- Constructing simplicial branched covers
- Pseudo-triangulations -- a survey
- On numbers of pseudo-triangulations
- ALGORITHMIC CONSTRUCTION OF KIRBY DIAGRAMS FOR BRANCHED COVERS
- scientific article; zbMATH DE number 28051
- scientific article; zbMATH DE number 3953844
- Triangulations and simplicial methods
- Enumerating pseudo-triangulations in the plane
- Branched coverings and Steiner ratio
Cites work
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 49719 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- scientific article; zbMATH DE number 1424303 (Why is no real title available?)
- scientific article; zbMATH DE number 1424307 (Why is no real title available?)
- scientific article; zbMATH DE number 5029228 (Why is no real title available?)
- scientific article; zbMATH DE number 3347270 (Why is no real title available?)
- scientific article; zbMATH DE number 2209712 (Why is no real title available?)
- scientific article; zbMATH DE number 2209740 (Why is no real title available?)
- scientific article; zbMATH DE number 3182580 (Why is no real title available?)
- A convex hull algorithm for discs, and applications
- An Output-Sensitive Convex Hull Algorithm for Planar Objects
- An efficient algorithm for determining the convex hull of a finite planar set
- Arrangements and Topological Planes
- Arrangements of double pseudolines
- Axioms and hulls
- Computing minimum length paths of a given homotopy class
- Convex hulls of objects bounded by algebraic curves
- Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
- Geometries on surfaces
- Geometry and topology for mesh generation
- Graphs on surfaces and their applications. Appendix by Don B. Zagier
- LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies
- Lectures in geometric combinatorics
- Multitriangulations, pseudotriangulations and primitive sorting networks
- Optimal output-sensitive convex hull algorithms in two and three dimensions
- Oriented Matroids
- Sorting by means of swappings
- THE VISIBILITY COMPLEX
- The Ultimate Planar Convex Hull Algorithm?
- Topologically sweeping an arrangement
- Topologically sweeping visibility complexes via pseudotriangulations
- Visibility Algorithms in the Plane
Cited in
(5)- Realization spaces of arrangements of convex bodies
- LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies
- Multitriangulations, pseudotriangulations and primitive sorting networks
- Algorithmic aspects of branched coverings I/V. Van Kampen's theorem for bisets
- Grassmannians and pseudosphere arrangements
This page was built for publication: Computing pseudotriangulations via branched coverings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714984)
