Name
Abstract | ||
|---|---|---|
We consider the problem of counting straight-edge triangulations of a given set P of n points in the plane. Until very recently it was not known whether the exact number of triangulations of P can be computed asymptotically faster than by enumerating all triangulations. We now know that the number of triangulations of P can be computed in O * ( 2 n ) time 9, which is less than the lower bound of ¿ ( 2.43 n ) on the number of triangulations of any point set 30. In this paper we address the question of whether one can approximately count triangulations in sub-exponential time. We present an algorithm with sub-exponential running time and sub-exponential approximation ratio, that is, denoting by ¿ the output of our algorithm and by c n the exact number of triangulations of P, for some positive constant c, we prove that c n ¿ ¿ ¿ c n ¿ 2 o ( n ) . This is the first algorithm that in sub-exponential time computes a ( 1 + o ( 1 ) ) -approximation of the base of the number of triangulations, more precisely, c ¿ ¿ 1 n ¿ ( 1 + o ( 1 ) ) c . Our algorithm can be adapted to approximately count other crossing-free structures on P, keeping the quality of approximation and running time intact. In this paper we show how to do this for matchings and spanning trees. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.comgeo.2014.12.006 | Comput. Geom. |
Keywords | DocType | Volume |
approximation algorithms | Journal | 48 |
Issue | ISSN | Citations |
5 | 0925-7721 | 3 |
PageRank | References | Authors |
0.39 | 26 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Victor Alvarez | 1 | 25 | 2.90 |
| Karl Bringmann | 2 | 427 | 30.13 |
| Saurabh Ray | 3 | 228 | 24.28 |
| Raimund Seidel | 4 | 44 | 3.18 |