A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
(2015) 42nd International Colloquium, ICALP 2015 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:
https://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
- 2015-07-06 - 2015-07-10
- external identifiers
-
- wos:000364317700064
- scopus:84950153799
- ISSN
- 0302-9743
- 1611-3349
- 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
- 2016-04-01 10:39:33
- date last changed
- 2024-01-06 21:56:04
@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 = {{0302-9743}},
keywords = {{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}},
doi = {{10.1007/978-3-662-47672-7_64}},
volume = {{9134}},
year = {{2015}},
}