A QPTAS for the Base of the Number of CrossingFree Structures on a Planar Point Set
(2015) 42nd International Colloquium, ICALP 2015 9134. p.785796 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 quasipolynomial 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 quasipolynomial 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:
http://lup.lub.lu.se/record/7866209
 author
 Karpinski, Marek ; Lingas, Andrzej ^{LU} and Sledneu, Dzmitry ^{LU}
 organization
 publishing date
 2015
 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
 host publication
 Automata, Languages, and Programming/Lecture notes in computer science
 volume
 9134
 pages
 785  796
 publisher
 Springer
 conference name
 42nd International Colloquium, ICALP 2015
 conference location
 Kyoto, Japan
 conference dates
 20150706  20150710
 external identifiers

 wos:000364317700064
 scopus:84950153799
 ISSN
 16113349
 03029743
 ISBN
 9783662476710
 DOI
 10.1007/9783662476727_64
 language
 English
 LU publication?
 yes
 id
 a34fed656ac344c7bd9e9358fe54d8e7 (old id 7866209)
 date added to LUP
 20160401 10:39:33
 date last changed
 20200112 04:55:29
@inproceedings{a34fed656ac344c7bd9e9358fe54d8e7, 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 quasipolynomial 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 = {9783662476710}, issn = {16113349}, language = {eng}, pages = {785796}, publisher = {Springer}, title = {A QPTAS for the Base of the Number of CrossingFree Structures on a Planar Point Set}, url = {http://dx.doi.org/10.1007/9783662476727_64}, doi = {10.1007/9783662476727_64}, volume = {9134}, year = {2015}, }