A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations

Original · EN

Let P² be a set of n points. In this paper we show two new algorithms, one to compute the number of triangulations of P, and one to compute the number of pseudo-triangulations of P. We show that our algorithms run in time O*(t(P)) and O*(pt(P)) respectively, where t(P) and pt(P) are the largest number of triangulation paths (T-paths) and pseudo-triangulations paths (PT-paths), respectively, that the algorithms encounter during their execution. Moreover, we show that t(P) = O*(9ⁿ), which is the first non-trivial bound on t(P) to be known. While there already are algorithms that count triangulations in O*(2ⁿ), and O*(3.1414ⁿ), there are sets of points where the number of T-paths is O(2ⁿ). In such cases the algorithm herein presented could potentially be faster. Furthermore, it is not clear whether the already-known algorithms can be modified to count pseudo-triangulations so that their running times remain O*(cⁿ), for some small constant c. Therefore, for counting pseudo-triangulations (and possibly other similar structures) our approach seems better.