
University of Bonn > Department of Computer Science > Chair V  
CSAPXReports 2014  Copyright 2014 University of Bonn, Department of Computer Science, 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 c^{n} , 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^{*}(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. We present the first quasipolynomial approximation scheme for the base of the number of triangulations of a planar point set. 

Last Change:
11/05/14 at 11:05:25
Deutsch 
University of Bonn > Department of Computer Science > Chair V 