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, Waterloo, August 6-10, 2001. Editor: T. Biedl; pp. 149-152.


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 (gzipped)
other papers about this subject
Last update: March 12, 2002.