A QPTAS for the base of the number of crossing-free structures on a planar point set
(2018) In Theoretical Computer Science 711. p.56-65- 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 crossing-free 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 crossing-free spanning trees runs in O (7.125n) time. The fastest known, non-trivial approximation algorithms for the number of triangulations of S and the number of crossing-free spanning trees of S, respectively, run in time subexponential in n. We present the first non-trivial approximation algorithms for these numbers running in quasi-polynomial 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 crossing-free 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 crossing-free spanning trees runs in O (7.125n) time. The fastest known, non-trivial approximation algorithms for the number of triangulations of S and the number of crossing-free spanning trees of S, respectively, run in time subexponential in n. We present the first non-trivial approximation algorithms for these numbers running in quasi-polynomial time. They yield the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of crossing-free spanning trees on S, respectively.
(Less)
- author
- Karpinski, Marek ; Lingas, Andrzej LU and Sledneu, Dzmitry LU
- organization
- publishing date
- 2018-02
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Approximation algorithms, Computational geometry, Counting spanning trees, Counting triangulations, Quasi-polynomial-time approximation scheme
- in
- Theoretical Computer Science
- volume
- 711
- pages
- 56 - 65
- publisher
- Elsevier
- external identifiers
-
- scopus:85034976918
- ISSN
- 0304-3975
- DOI
- 10.1016/j.tcs.2017.11.003
- language
- English
- LU publication?
- yes
- id
- af3773e6-9ab9-428c-bad0-a2d5f07cad18
- date added to LUP
- 2017-12-11 08:16:10
- date last changed
- 2022-03-17 02:54:18
@article{af3773e6-9ab9-428c-bad0-a2d5f07cad18,
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 crossing-free 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 crossing-free spanning trees runs in O (7.125n) time. The fastest known, non-trivial approximation algorithms for the number of triangulations of S and the number of crossing-free spanning trees of S, respectively, run in time subexponential in n. We present the first non-trivial approximation algorithms for these numbers running in quasi-polynomial time. They yield the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of crossing-free spanning trees on S, respectively.</p>}},
author = {{Karpinski, Marek and Lingas, Andrzej and Sledneu, Dzmitry}},
issn = {{0304-3975}},
keywords = {{Approximation algorithms; Computational geometry; Counting spanning trees; Counting triangulations; Quasi-polynomial-time approximation scheme}},
language = {{eng}},
pages = {{56--65}},
publisher = {{Elsevier}},
series = {{Theoretical Computer Science}},
title = {{A QPTAS for the base of the number of crossing-free structures on a planar point set}},
url = {{http://dx.doi.org/10.1016/j.tcs.2017.11.003}},
doi = {{10.1016/j.tcs.2017.11.003}},
volume = {{711}},
year = {{2018}},
}