A QPTAS for the Base of the Number of Triangulations of a Planar Point Set

preprint2014arXivOpen access

Abstract

The number of triangulations of a planar n point set is known to be cnc^n, where the base cc lies between 2.432.43 and 30.30. The fastest known algorithm for counting triangulations of a planar n point set runs in O∗(2n)O^*(2^n) time. The fastest known arbitrarily close approximation algorithm for the base of the number of triangulations of a planar n point set runs in time subexponential in n.n. We present the first quasi-polynomial approximation scheme for the base of the number of triangulations of a planar point set.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.