On the number of pseudo-triangulations of certain point sets

DOI10.1016/j.jcta.2007.06.002zbMath1133.68076arXivmath/0601747OpenAlexW2103342896WikidataQ59782361 ScholiaQ59782361MaRDI QIDQ2474495

Francisco Santos, Bettina Speckmann, David Orden, Oswin Aichholzer

Publication date: 6 March 2008

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

triangulationscountingpseudo-triangulationsdouble-chaindouble-circle

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (12)

Configurations of non-crossing rays and related problems ⋮ Counting with Borel's triangle ⋮ On the number of plane geometric graphs ⋮ Minimum weight pseudo-triangulations ⋮ On numbers of pseudo-triangulations ⋮ Multitriangulations, pseudotriangulations and primitive sorting networks ⋮ Borel generators ⋮ Counting polygon triangulations is hard ⋮ Catalan numbers, binary trees, and pointed pseudotriangulations ⋮ Unnamed Item ⋮ Empty pseudo-triangles in point sets ⋮ Lower bounds on the maximum number of non-crossing acyclic graphs

Uses Software

• OEIS

Cites Work

• Convexity minimizes pseudo-triangulations
• Combinatorial pseudo-triangulations
• Ray shooting in polygons using geodesic triangulations
• Enumerating a class of lattice paths
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• Allocating vertex \(\pi\)-guards in simple polygons via pseudo-triangulations
• The polytope of non-crossing graphs on a planar point set
• Planar minimally rigid graphs and pseudo-triangulations
• Topologically sweeping visibility complexes via pseudotriangulations
• A better upper bound on the number of triangulations of a planar point set
• A lower bound on the number of triangulations of planar point sets
• Minimal tangent visibility graphs
• Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations
• Singularity Analysis of Generating Functions
• On the number of plane graphs
• Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
• KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS
• Motzkin numbers
• Acute triangulations of polygons
• Algorithms and Data Structures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the number of pseudo-triangulations of certain point sets