Let $P\subset\mathbb{R}^{2}$ 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^{n})$, which is the first non-trivial bound on $t(P)$ to be known. While there already are algorithms that count triangulations in $O^{*}\left(2^n\right)$, and $O^{*}\left(3.1414^{n}\right)$, there are sets of points where the number of T-paths is $O(2^{n})$. 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^n)$, for some small constant $c\in\mathbb{R}$. Therefore, for counting pseudo-triangulations (and possibly other similar structures) our approach seems better.

Thanks. We have received your report. If we find this content to be in
violation of our guidelines,
we will remove it.

Ok