The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set

På svenska

Author

Summary, in English

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.

Department/s

Publishing year

2015

Language

English

Pages

785-796

Publication/Series

Automata, Languages, and Programming/Lecture notes in computer science

Volume

9134

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Keywords

  • Counting spanning trees of a planar point set
  • Counting triangulations of a planar point set
  • Approximation algorithms
  • Computational geometry

Conference name

42nd International Colloquium, ICALP 2015

Conference date

2015-07-06 - 2015-07-10

Conference place

Kyoto, Japan

Status

Published

ISBN/ISSN/Other

  • ISSN: 1611-3349
  • ISSN: 0302-9743
  • ISBN: 978-3-662-47671-0