Decomposition of Catalan numbers and convex polygon triangulations

Abstract

In this paper we present a method for Catalan number decomposition in the expressions of the form (2+i). This method gives convex polygon triangulations in Hurtado–Noy ordering. Therefore, we made a relationship between the expressions and the ordering mentioned above. The corresponding algorithm for Catalan number decomposition is developed and implemented in Java, as well as the algorithm which generates convex polygon triangulations. At the end, we have provided the comparison of Hurtado's algorithm and our algorithm based on the decomposition method.

Keywords:

• convex polygon triangulation
• Catalan number decomposition
• Hurtado–Noy algorithm

2010 AMS Subject Classifications:

• 68U05
• 65D18
• 68N15
• 97P40
• 11Y16

Acknowledgements

The authors gratefully acknowledge support from the research project 174033 of the Serbian Ministry of Science.