Computing pseudotriangulations via branched coverings

DOI10.1007/s00454-012-9447-zzbMath1267.68270arXiv1102.0151MaRDI QIDQ714984

Michel Pocchiola, Luc Habert

Publication date: 15 October 2012

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

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

zbMATH Keywords

convex hull; chirotope; visibility complex; pseudotriangulation; topological plane

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

57M50: General geometric structures on low-dimensional manifolds

52A10: Convex sets in (2) dimensions (including convex curves)

51A35: Non-Desarguesian affine and projective planes

Related Items

LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies, Multitriangulations, pseudotriangulations and primitive sorting networks, Grassmannians and pseudosphere arrangements, Realization spaces of arrangements of convex bodies

Cites Work

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