Counting triangulations of some
classes of subdivided convex polygons
(26 pages)
Abstract.
We compute the number of triangulations of a convex k-gon
each of whose sides is subdivided by r-1 points.
We find explicit formulas and generating functions,
and we determine the asymptotic behaviour of these numbers
as k and/or r tend to infinity.
We connect
these results with the question of finding
the planar set of points in general position
that has the minimum possible number of triangulations -
a well-known open problem from computational geometry.
The following versions are available:
Back to Christian Krattenthaler's
home page.