Triangulations of a convex polygon

Keehong Song
Pusan National University,South Korea
khsong@mathematica.co.kr

This is a Mathematica Notebook which finds and visualizes the triangulations of a convex polygon. As an example, 5-polygon has 5 triangulation as follows. 


In general, n-polygon has the triangulations of the n-2 Catalan number, that is, (1/(n - 1))(({{2 (n - 2)}, {n - 2}})).
References:
Grimaldi, R. Discrete and Combinatorial Mathematics, 3rd ed., Addison-Wesley,1994.

Counting binary tree

The number of binary trees with n nodes is (1/(n + 1))(({{2  n}, {n}}))

catalanNumber[n_] := Binomial[2  n, n]/(n + 1)

Generating binary tree

Generating  binary trees for traversal to find edges to be used in triangulations of a convex polygon, where the number of different binary trees is the Catalan number.

catalanTree[{}] := {{}}
catalanTree[{a_}] := {{a}}
\(catalanTree[l_List] := 
	
      Module[{m = Rest[l], i, elem1st = First[l]}, 
		Join @@ 
          Map[Insert[#, {elem1st}, {2}] &, 
		Table[
              Distribute[
		{catalanTree[Take[m, i]], 
		catalanTree[
                    Take[m, {i + 1, Length[m]}]]}, List], 
	{i, 0, 
                Length[m]}], {2}]]\)

Finding all the binary trees made out of the nodes,{1,2,3,4}, when parenthesis seen as the tree structure.

catalanTree[{1, 2, 3, 4}]

By flattening the tree structure above, we get the order in which a group of cars can  go in and out of the narrow-alley parking lot in an orderly fashion.

Flatten  /@  %

Length[%] == catalanNumber[4]

Finding edges involved in a triangulation  of a convex polygon

Depth first traversal is used to find the edges which conduce to the triangulations of a convex polygon.
There are three types of nodes in a given node of a tree: 
1.  both left and right children exist
2.  only right child exists
3.  only left child exists
These three types determines the patterns of the edges of a triangulation

NodeQ = Function[c, c =!= {}];
\(\(search[{lc_?NodeQ, {parent_}, rc_?NodeQ}, {l_, 
            r_}]
	 := \((\((AppendTo[storage, #] &)\) /@ 
	{{l, 
                l + Length[Flatten[lc]] + 1}, 
	{l + Length[Flatten[lc]] + 
                  1, r}}; 
search[lc, {l, l + Length[Flatten[lc]] + 1}]; 

          search[rc, {l + Length[Flatten[lc]] + 1, r}])\);\)\)
\(\(search[{lc_?NodeQ, {parent_}, {}}, {l_, r_}] := 
	\((AppendTo[
            storage, {l + 1, r}]; search[lc, {l + 1, r}])\);\)\)
\(\(search[{{}, {parent_}, rc_?NodeQ}, {l_, r_}] := 
	\((AppendTo[
            storage, {l, v[[r]]}]; 
          search[rc, {l, 
              v[[r]]}])\);\)
\)
\(triangleEdges[n_] := 

      Block[{storage = \(branches = {}\), v, m, trees}, 
	\ v = 
          RotateRight[Range[n + 2], 1]; 
	\ trees = 
          catalanTree[Range[n]]; 
	\ Table[
          search[trees[[m]], {2, 
              1}]; 
		AppendTo[branches, 
            storage]; 
		storage = {}, 
		{m, 1, 
            catalanNumber[n]}]; 
		branches]\)

We want to make sure that there is no duplicates in the set of edges for triangulations.

zigzag = triangleEdges[5];

Length@Union[Sort /@ zigzag] == Length[zigzag]

The following routine 'triangulation' does the physical triangulation by placing the line segments to the necessary positions in an n-gon.

\(triangulation[n_Integer, pairs_List] := 
	
      Module[{x = N[2  Pi/n], poly, vertices, edges}, 
		vertices = 
          Chop@Table[N[{Cos[x\ i], Sin[x\ i]}], {i, n}]; 
		poly = 
          Line /@ Partition[Append[vertices, First[vertices]], 2, 
              1]; 
		edges = 
          Line /@ \((\(vertices[\([#]\)] &\) /@ pairs)\); 
		Show[
          Graphics[{poly, edges}], 
		DisplayFunction -> Identity, 
          AspectRatio -> Automatic]
	]\)

Making the visualization process as a single function

In making a single function out of the process of visualizing triangulation,  a minor trouble is met due to a limitation of the built-in  'Partition' function:  it throws away the remainding parts after partitioning the given set to a  size. Appending the remainder at the end of the partition result solves the problem.

\(showTriangulation[n_Integer, gons_] := 
	
      Module[{pic}, 
	 (*If\ the\ size\ is\ too\ small, \ 
          do\ not\ partition*) 
	
        pic = If[n >= 5, 
	
            Append[Partition[gons, 15], 
Take[
                gons, \(-Mod[catalanNumber[n - 2], 15]\)]], gons]; 
	
        Show[GraphicsArray[pic], 
          DisplayFunction -> $DisplayFunction]]\)

An example for the case of 9-polygon

The number of triangulations of a n-polygon is, (1/(n - 1))(({{2 (n - 2)}, {n - 2}})).

size = 8;
edges = triangleEdges[size - 2];
tripic = triangulation[size, #] & /@ edges;
showTriangulation[size, tripic]

tripic // Length

catalanNumber[6]

Now we know that all the triangulations are accounted for.