Andrei Asinowski, Christian Krattenthaler and Toufik Mansour

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.