Euler polygon division algorithm

Question

I am trying to enumerate and display all possible divisions of an n-polygon into (n-2) triangles (as in the following mathworld picture)

Euler polygon division

I know how to count how many divisions (Catalan numbers, 1, 2, 5, 14, 42, ... ), but I am struggling to find a way to generate all the C(n-2) triangulations. Can anyone point to existing software implementation, or at least to an algorithm that generates these triangles?

Answer 1

See: Hurtado and Noy, Graph of triangulations of a convex polygon and tree of triangulations , Computational Geometry 13 (1999) pp179–188.

Section 3 of that paper gives a relatively straightforward method for constructing all triangulations of $n+1$-gons given all triangulations of $n$-gons.

Answer 2

You can use the formula to count the number of division to generate them.

Suppose you want to generate a division of a $n$-polygon whose vertices are 1,ドル 2, ..., n$. We know that there are $C_{n-2}$ such divisions (where $C_k$ is the $k$-th Catalan's number). What we need to do is:

• chose 2ドル\leqslant k\leqslant n-1$ the other vertex of the triangle with edge $\{1, n\}$;
• chose a division of the polygon with vertices 1,ドル 2, ..., k$;
• chose a division of the polygon with vertices $k, k+1, ..., n$.

Suppose you want to generate the $i$-th division of the $n$-polygon, 1ドル\leqslant i\leqslant C_{n-2}$. Since we know that $C_{n-2} = \sum\limits_{j=2}^{n-1}C_{j-2}C_{n-1-j}$, we have a way to chose the value of $k$: chose the minimum $k$ such that $i\leqslant \sum\limits_{j=2}^kC_{j-2}C_{n-1-j}$.

We then need to chose the number $i_1$ of the division of the polygon 1,ドル 2, ..., k$ and the number $i_2$ of the division of the polygon $k, k+1, ..., n$. Picking $i_1 = i\mod C_{k-2}$ and $i_2 = \left\lfloor \frac{i}{C_{k-2}}\right\rfloor$ will do the trick.

This gives the idea of a recursive algorithm to generate divisions. Note that the base case here is the polygon with $n=2$ (a simple edge).