Counting Triangulations and Other Crossing-Free Structures via Onion Layers

Let P be a set of n points in the plane. A crossing-free structure on P is a straight-edge plane graph with vertex set P. Examples of crossing-free structures include triangulations and spanning cycles, also known as polygonalizations. In recent years, there has been a large amount of research trying to bound the number of such structures; in particular, bounding the number of (crossing-free) triangulations spanned by P has received considerable attention. It is currently known that every set of n points has at most O(30ⁿ) and at least Ω(2.43ⁿ) triangulations. However, much less is known about the algorithmic problem of counting crossing-free structures of a given set P. In this paper, we develop a general technique for computing the number of crossing-free structures of an input set P. We apply the technique to obtain algorithms for computing the number of triangulations, matchings, and spanning cycles of P. The running time of our algorithms is upper-bounded by n^O(k), where k is the number of onion layers of P. In particular, for k=O(1) our algorithms run in polynomial time. Additionally, we show that our algorithm for counting triangulations in the worst case over all k takes time O^∗(3.1414ⁿ). [In the notations Ω^∗(·),O^∗(·), and Θ^∗(·), we neglect polynomial terms and we just present the dominating exponential term.] Given that there are several well-studied configurations of points with at least Ω(3.47ⁿ) triangulations, and some even with Ω(8.65ⁿ) triangulations, our algorithm asymptotically outperforms any enumeration algorithm for such instances. We also show that our techniques are general enough to solve the Restricted-Triangulation-Counting-Problem, which we prove to be W[2]-hard in the parameter $$k$$k. This implies that in order to be fixed-parameter tractable, our general algorithm must rely on additional properties that are specific to the considered class of crossing-free structures.