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

MaRDI QIDQ6247223zbMATH OpenFDO

Authors Victor Alvarez, Karl Bringmann, Saurabh Ray

Publication date 11 December 2013

Abstract: Let $Psubsetmathbb{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^{\ast }(t(P))$ and $O^{\ast }(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^{\ast }(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^{\ast }left(2^{n}ight)$, and $O^{\ast }left(3.1414^{n}ight)$, 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^{\ast }(c^n)$, for some small constant $cinmathbbR$. Therefore, for counting pseudo-triangulations (and possibly other similar structures) our approach seems better.

This page was built for publication: A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6247223)