On the number of pseudo-triangulations of certain point sets

DOI10.1016/J.JCTA.2007.06.002zbMATH Open1133.68076arXivmath/0601747OpenAlexW2103342896WikidataQ59782361 ScholiaQ59782361MaRDI QIDQ2474495FDOQ2474495

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)

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.

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

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

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)

Cites Work

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

Cited In (17)

• Title not available (Why is that?)
• 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
• Lower bounds on the maximum number of non-crossing acyclic graphs
• On numbers of pseudo-triangulations
• 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

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)