Counting triangulations and other crossing-free structures approximately (Q2341692)

The authors consider the problem of counting straight-edge triangulations of a given set \(P\) on \( n\) points in the plane. They use asymptotic analysis to compute the complexity of a new algorithm proposed by them. This new algorithm can be adapted to approximately count other crossing-free structures of \( P\), keeping the quality of approximation and running time intact. This new algorithm has a sub-exponential running time and sub-exponential approximation ratio.