A simple aggregative algorithm for counting triangulations of planar point sets and related problems

摘要: We give an algorithm that determines the number (S) of straight line triangulations a set S n points in plane worst case time O(n2 2n). This is first provably faster than enumeration, since known to be Ω(2.43n) for any points. Our requires exponential space.The generalizes counting all are constrained contain given edges. It can also used compute optimal triangulation (unconstrained or constrained) reasonably wide class optimality criteria (that includes e.g. minimum weight triangulations). Finally, approach random generation according perfect uniform distribution.The has been implement and substantially existing methods on variety inputs.