Counting triangulations and other crossing-free structures approximately

摘要: We consider the problem of counting straight-edge triangulations a given set P n points in plane. Until very recently it was not known whether exact number can be computed asymptotically faster than by enumerating all triangulations. now know that O * ( 2 ) time 9, which is less lower bound ? 2.43 on any point 30. In this paper we address question one approximately count sub-exponential time. present an algorithm with running and approximation ratio, is, denoting output our c P, for some positive constant c, prove o . This first computes 1 + -approximation base triangulations, more precisely, Our adapted to other crossing-free structures keeping quality intact. show how do matchings spanning trees.