On the number of pseudo-triangulations of certain point sets

DOI10.1016/J.JCTA.2007.06.002MaRDI QIDQ2474495zbMATH OpenOpenAlexWikidataFDO

Authors David Orden, Bettina Speckmann, Oswin Aichholzer, Francisco Santos

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, https://idus.us.es/xmlui/handle/11441/55105

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)

Abstract: We pose a monotonicity conjecture on the number of pseudo-triangulations of any planar point set, and check it on two prominent families of point sets, namely the so-called double circle and double chain. The latter has asymptotically $12^n{n}^{Theta(1)}$ pointed pseudo-triangulations, which lies significantly above the maximum number of triangulations in a planar point set known so far.

Recommendations

• On numbers of pseudo-triangulations
• Convexity minimizes pseudo-triangulations
• Enumerating pseudo-triangulations in the plane
• An improved lower bound on the minimum number of triangulations
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1409186 (Why is no real title available?)
• scientific article; zbMATH DE number 2209740 (Why is no real title available?)
• 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
• Acute triangulations of polygons
• Algorithms and Data Structures
• Allocating vertex \(\pi\)-guards in simple polygons via pseudo-triangulations
• Combinatorial pseudo-triangulations
• Convexity minimizes pseudo-triangulations
• Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations
• Enumerating a class of lattice paths
• KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• Minimal tangent visibility graphs
• Motzkin numbers
• On the number of plane graphs
• Planar minimally rigid graphs and pseudo-triangulations
• Pseudo-triangulations -- a survey
• Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
• Ray shooting in polygons using geodesic triangulations
• Singularity Analysis of Generating Functions
• The On-Line Encyclopedia of Integer Sequences
• The polytope of non-crossing graphs on a planar point set
• Topologically sweeping visibility complexes via pseudotriangulations

Cited in

(17)

• scientific article; zbMATH DE number 7559233 (Why is no real title available?)
• Configurations of non-crossing rays and related problems
• Multitriangulations, pseudotriangulations and primitive sorting networks
• Counting with Borel's triangle
• On the number of triangles in simple arrangements of pseudolines in the real projective plane
• The Number of Triangulations on Planar Point Sets
• Catalan numbers, binary trees, and pointed pseudotriangulations
• On simple arrangements of lines and pseudo-lines in P^2 and R^2 with the maximum number of triangles
• On numbers of pseudo-triangulations
• Lower bounds on the maximum number of non-crossing acyclic graphs
• Minimum weight pseudo-triangulations
• Empty pseudo-triangles in point sets
• Counting polygon triangulations is hard
• Enumerating pseudo-triangulations in the plane
• On the number of plane geometric graphs
• Borel generators
• Levi's Lemma, pseudolinear drawings of , and empty triangles

Describes a project that uses

Uses Software

• OEIS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2474495)