A QPTAS for the base of the number of crossingfree structures on a planar point set
(2017) In Theoretical Computer Science Abstract
The number of triangulations of a planar n point set S is known to be cn, where the base c lies between 2.43 and 30. Similarly, the number of crossingfree spanning trees on S is known to be dn, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in 2(1+o(1))nlog n time while that for counting crossingfree spanning trees runs in O (7.125n) time. The fastest known, nontrivial approximation algorithms for the number of triangulations of S and the number of crossingfree spanning trees of S, respectively, run in time subexponential in n. We present the first nontrivial approximation algorithms for these numbers running in quasipolynomial time. They yield the first... (More)
The number of triangulations of a planar n point set S is known to be cn, where the base c lies between 2.43 and 30. Similarly, the number of crossingfree spanning trees on S is known to be dn, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in 2(1+o(1))nlog n time while that for counting crossingfree spanning trees runs in O (7.125n) time. The fastest known, nontrivial approximation algorithms for the number of triangulations of S and the number of crossingfree spanning trees of S, respectively, run in time subexponential in n. We present the first nontrivial approximation algorithms for these numbers running in quasipolynomial time. They yield the first quasipolynomial approximation schemes for the base of the number of triangulations of S and the base of the number of crossingfree spanning trees on S, respectively.
(Less)
 author
 Karpinski, Marek; Lingas, Andrzej ^{LU} and Sledneu, Dzmitry ^{LU}
 organization
 publishing date
 20171116
 type
 Contribution to journal
 publication status
 epub
 subject
 keywords
 Approximation algorithms, Computational geometry, Counting spanning trees, Counting triangulations, Quasipolynomialtime approximation scheme
 in
 Theoretical Computer Science
 publisher
 Elsevier
 external identifiers

 scopus:85034976918
 ISSN
 03043975
 DOI
 10.1016/j.tcs.2017.11.003
 language
 English
 LU publication?
 yes
 id
 af3773e69ab9428cbad0a2d5f07cad18
 date added to LUP
 20171211 08:16:10
 date last changed
 20180107 12:28:03
@article{af3773e69ab9428cbad0a2d5f07cad18, abstract = {<p>The number of triangulations of a planar n point set S is known to be cn, where the base c lies between 2.43 and 30. Similarly, the number of crossingfree spanning trees on S is known to be dn, where the base d lies between 6.75 and 141.07. The fastest known algorithm for counting triangulations of S runs in 2(1+o(1))nlog n time while that for counting crossingfree spanning trees runs in O (7.125n) time. The fastest known, nontrivial approximation algorithms for the number of triangulations of S and the number of crossingfree spanning trees of S, respectively, run in time subexponential in n. We present the first nontrivial approximation algorithms for these numbers running in quasipolynomial time. They yield the first quasipolynomial approximation schemes for the base of the number of triangulations of S and the base of the number of crossingfree spanning trees on S, respectively.</p>}, author = {Karpinski, Marek and Lingas, Andrzej and Sledneu, Dzmitry}, issn = {03043975}, keyword = {Approximation algorithms,Computational geometry,Counting spanning trees,Counting triangulations,Quasipolynomialtime approximation scheme}, language = {eng}, month = {11}, publisher = {Elsevier}, series = {Theoretical Computer Science}, title = {A QPTAS for the base of the number of crossingfree structures on a planar point set}, url = {http://dx.doi.org/10.1016/j.tcs.2017.11.003}, year = {2017}, }