Advanced

A QPTAS for the base of the number of crossing-free structures on a planar point set

Karpinski, Marek; Lingas, Andrzej LU and Sledneu, Dzmitry LU (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 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)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
epub
subject
keywords
Approximation algorithms, Computational geometry, Counting spanning trees, Counting triangulations, Quasi-polynomial-time approximation scheme
in
Theoretical Computer Science
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
2018-01-07 12:28:03
@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},
  keyword      = {Approximation algorithms,Computational geometry,Counting spanning trees,Counting triangulations,Quasi-polynomial-time approximation scheme},
  language     = {eng},
  month        = {11},
  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},
  year         = {2017},
}