2013/12/11 by Victor Alvarez, Alvarez, Victor, Karl Bringmann +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #I.3.5 #cs.CG #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1312.3188
38 pages, 48 figures. Submitted to journal
arxiv created 2013/12/11 · arxiv updated 2013/12/12
Let P⊂ℝ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*(9n), which is the first non-trivial bound on t(P) to be known. While there already are algorithms that count triangulations in O*(2n), and O*(3.1414n), there are sets of points where the number of T-paths is O(2n). 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*(cn), for some small constant c∈ℝ. Therefore, for counting pseudo-triangulations (and possibly other similar structures) our approach seems better.