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
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.
Last update: March 12, 2002.