On the Number of Pseudo-Triangulations of Certain Point Sets

O. Aichholzer, D. Orden, F. Santos, and B. Speckmann

Abstract:

We compute the exact number of pseudo-triangulations for two prominent point sets, namely the so-called double circle and the double chain. We also derive a new asymptotic lower bound for the maximal number of pseudo-triangulations which lies significantly above the related bound for triangulations.

Reference: O. Aichholzer, D. Orden, F. Santos, and B. Speckmann. On the number of pseudo-triangulations of certain point sets. In Proc. $15th$ Annual Canadian Conference on Computational Geometry CCCG 2003, pages 141-144, Halifax, Nova Scotia, Canada, 2003.