A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set

DOI10.1007/978-3-662-47672-7_64zbMath1386.68201arXiv1411.0544OpenAlexW1618980576MaRDI QIDQ3448837

Dzmitry Sledneu, Andrzej Lingas, Marek Karpinski

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

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
• Counting triangulations and other crossing-free structures approximately
• Counting Plane Graphs: Flippability and Its Applications
• Bounds on the Maximum Multiplicity of Some Common Geometric Graphs
• Counting crossing-free structures
• 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