Counting Polygon Triangulations is Hard

Abstract

We prove that it is $\#\mathsf{P}$-complete to count the triangulations of a (non-simple) polygon.

24 pages, 11 figures. Expanded version of a paper from Proc. 35th International Symposium on Computational Geometry

Cited by in corpus (3)

• Computational complexity of counting coincidences
• Non-crossing Hamiltonian Paths and Cycles in Output-Polynomial Time
• Computational Complexities of Folding