hide
Free keywords:
Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Combinatorics, math.CO
Abstract:
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.
