Computing pseudotriangulations via branched coverings

DOI10.1007/S00454-012-9447-ZzbMATH Open1267.68270arXiv1102.0151OpenAlexW3099684872MaRDI QIDQ714984FDOQ714984

Authors: Luc Habert, Michel Pocchiola 

Publication date: 15 October 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1102.0151

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

zbMATH Keywords

convex hullchirotopevisibility complexpseudotriangulationtopological plane

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Oriented Matroids
• An efficient algorithm for determining the convex hull of a finite planar set
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Arrangements of double pseudolines
• Graphs on surfaces and their applications. Appendix by Don B. Zagier
• Geometries on surfaces
• Geometry and topology for mesh generation
• Multitriangulations, pseudotriangulations and primitive sorting networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Topologically sweeping an arrangement
• Title not available (Why is that?)
• Visibility Algorithms in the Plane
• Lectures in geometric combinatorics
• Title not available (Why is that?)
• Axioms and hulls
• LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies
• Arrangements and Topological Planes
• Title not available (Why is that?)
• The Ultimate Planar Convex Hull Algorithm?
• An Output-Sensitive Convex Hull Algorithm for Planar Objects
• Topologically sweeping visibility complexes via pseudotriangulations
• THE VISIBILITY COMPLEX
• Sorting by means of swappings
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Title not available (Why is that?)
• Computing minimum length paths of a given homotopy class
• A convex hull algorithm for discs, and applications
• Convex hulls of objects bounded by algebraic curves
• Title not available (Why is that?)

Cited In (5)

• Algorithmic aspects of branched coverings I/V. Van Kampen's theorem for bisets
• Multitriangulations, pseudotriangulations and primitive sorting networks
• Realization spaces of arrangements of convex bodies
• Grassmannians and pseudosphere arrangements
• LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies

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)