Advanced

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

Karpinski, Marek; Lingas, Andrzej LU and Sledneu, Dzmitry LU (2015) 42nd International Colloquium, ICALP 2015 In Automata, Languages, and Programming/Lecture notes in computer science 9134. p.785-796
Abstract
The number of triangulations of a planar n point set S is known to be c^n, where the base c lies between 2.43 and 30. Similarly, the number of spanning trees on S is known to be d^n, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in O^∗(2^n) time while that for counting spanning trees runs in O^∗(7.125^n) time. The fastest known arbitrarily close approximation algorithms for the base of the number of triangulations of S and the base of the number of spanning trees of S, respectively, run in time subexponential in n. We present the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of spanning trees on S,... (More)
The number of triangulations of a planar n point set S is known to be c^n, where the base c lies between 2.43 and 30. Similarly, the number of spanning trees on S is known to be d^n, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in O^∗(2^n) time while that for counting spanning trees runs in O^∗(7.125^n) time. The fastest known arbitrarily close approximation algorithms for the base of the number of triangulations of S and the base of the number of spanning trees of S, respectively, run in time subexponential in n. We present the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of spanning trees on S, respectively. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Counting spanning trees of a planar point set, Counting triangulations of a planar point set, Approximation algorithms, Computational geometry
in
Automata, Languages, and Programming/Lecture notes in computer science
volume
9134
pages
785 - 796
publisher
Springer
conference name
42nd International Colloquium, ICALP 2015
external identifiers
  • wos:000364317700064
  • scopus:84950153799
ISSN
1611-3349
0302-9743
ISBN
978-3-662-47671-0
DOI
10.1007/978-3-662-47672-7_64
language
English
LU publication?
yes
id
a34fed65-6ac3-44c7-bd9e-9358fe54d8e7 (old id 7866209)
date added to LUP
2015-09-14 12:38:22
date last changed
2017-01-01 03:47:03
@inproceedings{a34fed65-6ac3-44c7-bd9e-9358fe54d8e7,
  abstract     = {The number of triangulations of a planar n point set S is known to be c^n, where the base c lies between 2.43 and 30. Similarly, the number of spanning trees on S is known to be d^n, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in O^∗(2^n) time while that for counting spanning trees runs in O^∗(7.125^n) time. The fastest known arbitrarily close approximation algorithms for the base of the number of triangulations of S and the base of the number of spanning trees of S, respectively, run in time subexponential in n. We present the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of spanning trees on S, respectively.},
  author       = {Karpinski, Marek and Lingas, Andrzej and Sledneu, Dzmitry},
  booktitle    = {Automata, Languages, and Programming/Lecture notes in computer science},
  isbn         = {978-3-662-47671-0},
  issn         = {1611-3349},
  keyword      = {Counting spanning trees of a planar point set,Counting triangulations of a planar point set,Approximation algorithms,Computational geometry},
  language     = {eng},
  pages        = {785--796},
  publisher    = {Springer},
  title        = {A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set},
  url          = {http://dx.doi.org/10.1007/978-3-662-47672-7_64},
  volume       = {9134},
  year         = {2015},
}