Counting triangulations and other crossing-free structures approximately

DOI10.1016/j.comgeo.2014.12.006zbMath1316.65027arXiv1404.0261OpenAlexW2055728458MaRDI QIDQ2341692

Raimund Seidel, Karl Bringmann, Saurabh Ray, Victor Alvarez

Publication date: 27 April 2015

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

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

zbMATH Keywords

triangulationscounting algorithmsalgorithmic geometryapproximation algoritmscrossing free structures

Mathematics Subject Classification ID

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

Related Items

A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set, Convex Polygons in Geometric Triangulations, Convex Polygons in Geometric Triangulations, A QPTAS for the base of the number of crossing-free structures on a planar point set, Counting polygon triangulations is hard, Unnamed Item, A Census of Plane Graphs with Polyline Edges, Counting triangulations and other crossing-free structures via onion layers

Cites Work

• Unnamed Item
• Counting triangulations of planar point sets
• On degrees in random triangulations of point sets
• Finding small simple cycle separators for 2-connected planar graphs
• Analytic combinatorics of non-crossing configurations
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• An efficient algorithm for enumeration of triangulations
• 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
• Reverse search for enumeration
• Reduced constants for simple cycle graph separation
• Counting triangulations and other crossing-free structures via onion layers
• On the number of plane geometric graphs
• Triangulations and applications
• Counting Plane Graphs: Flippability and Its Applications
• Bounds on the Maximum Multiplicity of Some Common Geometric Graphs
• Counting crossing-free structures
• Counting Plane Graphs with Exponential Speed-Up
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• Counting and Enumerating Crossing-free Geometric Graphs
• A simple aggregative algorithm for counting triangulations of planar point sets and related problems
• Fast enumeration algorithms for non-crossing geometric graphs
• Algorithms and Data Structures
• Enumerating triangulation paths