A QPTAS for the base of the number of crossing-free structures on a planar point set
type: Item
instance of: scholarly article
title: A QPTAS for the base of the number of crossing-free structures on a planar point set
zbMATH Open document ID: 1386.68202
author: Marek Karpinski
author: Andrzej Lingas
author: Dzmitry Sledneu
published in: Theoretical Computer Science
publication date: 2018-02-16T00:00:00Z
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6839810
zbMATH Keywords: computational geometry
zbMATH Keywords: approximation algorithms
zbMATH Keywords: counting triangulations
zbMATH Keywords: counting spanning trees
zbMATH Keywords: quasi-polynomial-time approximation scheme
MaRDI profile type: Publication
full work available at URL: j.tcs.2017.11.003
OpenAlex ID: W2770043005
cites work: A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
cites work: Counting triangulations and other crossing-free structures approximately
cites work: Counting crossing-free structures
cites work: A simple aggregative algorithm for counting triangulations of planar point sets and related problems
cites work: Lower bounds on the number of crossing-free subgraphs of \(K_N\)
cites work: Analytic combinatorics of non-crossing configurations
cites work: Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
cites work: Counting Plane Graphs: Flippability and Its Applications
cites work: Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems
cites work: Finding small simple cycle separators for 2-connected planar graphs
cites work: Counting triangulations of planar point sets
cites work: On degrees in random triangulations of point sets
cites work: Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
cites work: On the Number of Crossing‐Free Matchings, Cycles, and Partitions
cites work: Counting and Enumerating Crossing-free Geometric Graphs
DOI: 10.1016/J.TCS.2017.11.003
description: scientific article; zbMATH DE number 6839810