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