Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems

Dániel Marx, Tillmann Miltzow

Given a set of $n$ points $S$ in the plane, a triangulation $T$ of $S$ is a maximal set of non-crossing segments with endpoints in $S$. We present an algorithm that computes the nu…