Counting polygon triangulations is hard (Q2223620)

There are many counting problems in discrete geometry for which we know neither a polynomial-time algorithm nor a hardness proof. For example, we do not know the complexity of counting triangulations, planar graphs, non-crossing Hamiltonian cycles, etc. In fact, in computational geometry, only a small number of problems have been shown to be \(\#P\)-complete or \(\#P\)-hard. In this paper, it is proven that counting the triangulations of polygons is a \(\#P\)-complete problem. The polygons constructed in the hardness proof have vertices with integer coordinates of polynomial magnitude. They have holes, to count the triangulations of a simple polygon in polynomial time by dynamic programming.The strategy was to develop a polynomial-time counting reduction from the problem of counting independent sets in planar graphs, which was proved to be \(\#P\)-complete.