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

Roland Bacher

started in september 04, last update: september 04

Let $C$ be the convex hull of a finite subset ${\mathcal P}\subset {\mathbf R}^2$ of points in the plane. It is in general difficult to count the number of (Euclidean) triangulations of $C$ with all vertices in ${\mathcal {P}}$. If all points are extremal (the convex hull decreases strictly by removing any point of ${\mathcal {P}}$) the result is however well known and given by the $(n-2)-$th Catalan number $C_{n-2}={{2n-4}\choose {n-2}}/(n-1)=\frac{(2n-4)!}{(n-2)!\ (n-1)!}$ where $n$ is the number of points in ${\mathcal P}$.

This result can be extended to points in weakly convex position: Consider a polygone with $k$ sides. Suppose these sides are subdivided by $a_1-1,a_2-1,\dots, a_k-1$ additional points. We consider the configuration ${\mathcal P}$ of these $a_1+a_2+\dots+a_k$ points. They are all on the boundary of the convex hull of ${\mathcal P}$ but only $k$ of them (the vertices of the polygon) are extremal. The number of triangulations using all points in ${\mathcal P}$ as vertices can then be computed as follows:

Set

$$p_n=\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^k{{n-k}\choose {k}}t^{n-k}\in {\mathbf Z}[t]$$

and consider the product

$$Q=p_{a_1}p_{a_2}\dots,p_{a_k}\in{\mathbf Z}[t]\ .$$

The number of triangulations of ${\mathcal P}$ is then given by

$$\langle Q,(C_{n-2})\rangle$$

where $\langle Q,(C_{n-2})\rangle$ denotes the linear application from $t^2{\mathbf Z}[t]$ into ${\mathbf Z}$ which is defined by $\langle t^k,(C_{n-2})\rangle=C_{k-2}$.

A similar formula exists for counting triangulations of the convex hull of ${\mathcal C}$ which use perhaps only a subset of all points: replace the polynomial $p_n$ by $\sum_{k=1}^n p_k$.

A proof of this can be found in my preprint Counting Triangulations of Configurations (math.CO/0310206 on the arXiv).