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

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

• 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
• Unnamed Item