Next: Bibliography

# Triangulating the hull of a finite number of points in convex position

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

and consider the product

The number of triangulations of is then given by

where denotes the linear application from into which is defined by .

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).

Next: Bibliography
Roland Bacher 2004-09-13