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

被引：2

作者：

Karpinski, Marek ^{[1
]}

Lingas, Andrzej ^{[2
]}

Sledneu, Dzmitry ^{[3
]}

机构：

[1] Univ Bonn, Dept Comp Sci, Bonn, Germany

[2] Lund Univ, Dept Comp Sci, Lund, Sweden

[3] Lund Univ, Ctr Math Sci, Lund, Sweden

来源：

THEORETICAL COMPUTER SCIENCE | 2018年 / 711卷

基金：

瑞典研究理事会;

关键词：

Computational geometry; Approximation algorithms; Counting triangulations; Counting spanning trees; Quasi-polynomial-time approximation scheme; TRIANGULATIONS; MATCHINGS; GRAPHS; CYCLES;

D O I：

10.1016/j.tcs.2017.11.003

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 crossing-free 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 2((1+o(1))root n log n) time while that for counting crossing-free spanning trees runs in O*(7.125(n)) time. The fastest known, nontrivial 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. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：56 / 65

页数：10