Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2014 Copyright 2014 Universität Bonn, Institut für Informatik, Abt. V
89156

29.09.2014

A QPTAS for the Base of the Number of Triangulations of a Planar Point Set
Marek Karpinski, Andrzej Lingas and Dzmitry Sledneu
[Download PostScript] [Download PDF]

The number of triangulations of a planar n point set is known to be cn , where the base c lies between 2.43 and 30. The fastest known algorithm for counting triangulations of a planar n point set runs in O*(2n) 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. We present the first quasi-polynomial approximation scheme for the base of the number of triangulations of a planar point set.

Last Change: 11/05/14 at 11:05:25
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope