A QPTAS for the base of the number of crossingfree structures on a planar point set
Research output: Contribution to journal › Article
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 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.
Details
Authors  

Organisations  
External organisations 

Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Pages (fromto)  5665 
Journal  Theoretical Computer Science 
Volume  711 
Early online date  2017 Nov 16 
Publication status  Published  2018 Feb 
Publication category  Research 
Peerreviewed  Yes 