A QPTAS for the base of the number of crossing-free structures on a planar point set
From MaRDI portal
Publication:1698728
DOI10.1016/j.tcs.2017.11.003zbMath1386.68202MaRDI 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
computational geometry; approximation algorithms; counting spanning trees; counting triangulations; quasi-polynomial-time approximation scheme
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W25: Approximation algorithms
Related Items
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
