A QPTAS for the base of the number of crossing-free structures on a planar point set

DOI10.1016/j.tcs.2017.11.003zbMath1386.68202OpenAlexW2770043005MaRDI QIDQ1698728

Marek Karpinski, Dzmitry Sledneu, Andrzej Lingas

Publication date: 16 February 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.11.003

zbMATH Keywords

computational geometryapproximation algorithmscounting spanning treescounting triangulationsquasi-polynomial-time approximation scheme

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

Counting polygon triangulations is hard, Unnamed Item

Cites Work

• 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\)
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Counting triangulations and other crossing-free structures approximately
• Counting Plane Graphs: Flippability and Its Applications
• Counting crossing-free structures
• Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• Counting and Enumerating Crossing-free Geometric Graphs
• Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
• A simple aggregative algorithm for counting triangulations of planar point sets and related problems
• A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices