A lower bound on the number of triangulations of planar point sets

DOI10.1016/J.COMGEO.2004.02.003zbMath1061.65013OpenAlexW2160689382MaRDI QIDQ1882855

Marc Noy, Oswin Aichholzer, Ferran Hurtado

Publication date: 1 October 2004

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2004.02.003

zbMATH Keywords

triangulationscounting

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (23)

Configurations of non-crossing rays and related problems ⋮ On the number of plane geometric graphs ⋮ On crossing-families in planar point sets ⋮ Abstract order type extension and new results on the rectilinear crossing number ⋮ Convexity minimizes pseudo-triangulations ⋮ Computing the flip distance between triangulations ⋮ The Mathematics of Ferran Hurtado: A Brief Survey ⋮ Counting polygon triangulations is hard ⋮ Counting triangulations of balanced subdivisions of convex polygons ⋮ Counting triangulations of some classes of subdivided convex polygons ⋮ On the number of pseudo-triangulations of certain point sets ⋮ On degrees in random triangulations of point sets ⋮ Unnamed Item ⋮ Improved upper bounds on the reflexivity of point sets ⋮ Unnamed Item ⋮ An improved FPT algorithm for the flip distance problem ⋮ EMBEDDING THE DOUBLE CIRCLE IN A SQUARE GRID OF MINIMUM SIZE ⋮ A new lower bound on the maximum number of plane graphs using production matrices ⋮ Counting triangulations and other crossing-free structures approximately ⋮ Connectivity of triangulation flip graphs in the plane ⋮ On the numerical implementation of variational arbitrary Lagrangian–Eulerian (VALE) formulations ⋮ Minimum number of partial triangulations ⋮ Counting triangulations and other crossing-free structures via onion layers

Cites Work

• Unnamed Item
• Convexity minimizes pseudo-triangulations
• Crossing families
• Generation of oriented matroids --- a graph theoretical approach
• Improved bounds for planar \(k\)-sets and related problems
• Note on the Erdős-Szekeres theorem
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• Enumerating order types for small point sets with applications
• A better upper bound on the number of triangulations of a planar point set
• Reverse search for enumeration
• SIMULTANEOUS EDGE FLIPPING IN TRIANGULATIONS

This page was built for publication: A lower bound on the number of triangulations of planar point sets