Dana Randall, Günter Rote, Francisco Santos, and Jack Snoeyink:

Counting triangulations and pseudo-triangulations of wheels

In: Proceedings of the 13th Canadian Conference on Computational Geometry (CCCG'01), Waterloo, August 6–10, 2001. Editor: T. Biedl; pp. 149–152.  →BibTeX


Motivated by several open questions on triangulations and pseudotriangulations,we give closed form expressions for the number of triangulations and the number of minimum pseudo-triangulations of n points in wheel configurations, that is, with n−1 in convex position.Although the numbers of triangulations and pseudotriangulations vary depending on the placement of the interior point, their difference is always the (n−2)nd Catalan number.
We also prove an inequality #PT <= 3i#T for the numbers of minimum pseudo-triangulations and triangulations of any point configuration with i interior points.
  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: March 12, 2002.