Roland Bacher
started in september 04, last update: september 04
Let be the convex hull of a finite subset of points in the plane. It is in general difficult to count the number of (Euclidean) triangulations of with all vertices in . If all points are extremal (the convex hull decreases strictly by removing any point of ) the result is however well known and given by the th Catalan number where is the number of points in .
This result can be extended to points in weakly convex position: Consider a polygone with sides. Suppose these sides are subdivided by additional points. We consider the configuration of these points. They are all on the boundary of the convex hull of but only of them (the vertices of the polygon) are extremal. The number of triangulations using all points in as vertices can then be computed as follows:
Set
A similar formula exists for counting triangulations of the convex hull of which use perhaps only a subset of all points: replace the polynomial by .
A proof of this can be found in my preprint Counting Triangulations of Configurations (math.CO/0310206 on the arXiv).