Convex polygon triangulation based on planted trivalent binary tree and ballot problem
Convex polygon triangulation based on planted trivalent binary tree and ballot problem
This paper presents a new technique of generation of convex polygon triangulation based on planted trivalentbinary tree and ballot notation. The properties of the Catalan numbers were examined and their decomposition andapplication in developing the hierarchy and triangulation trees were analyzed. The method of storage and processing oftriangulation was constructed on the basis of movements through the polygon. This method was derived from verticesand leaves of the planted trivalent binary tree. The research subject of the paper is analysis and comparison of aconstructed method for solving of convex polygon triangulation problem with other methods and generating graphicalrepresentation. The application code of the algorithms was done in the Java programming language.
___
- [1] Koshy T. Catalan Numbers with Applications. New York, NY, USA: Oxford University Press,2009.
- [2] Even S. Graph Algorithms. New York, NY, USA: Cambridge University Press, 2011.
- [3] Goodman JE, O’Rourke J. Handbook of Discrete and Computational Geometry. New York, NY, USA: Chapman
and Hall and CRC Press, 2004.
- [4] O’Rourke J. Computational Geometry in C. 2nd ed. Cambridge, UK: Cambridge University Press, 1997.
- [5] Preparata F, Shamos MI. Computational Geometry: An introduction. Berlin, Germany: Springer-Verlag, 1985.
- [6] Koshy T. Discrete Mathematics with Applications. Burlington, MA, USA: Elsevier Academic Press, 2004.
- [7] Hurtado F, Noy M. Graph of triangulations of a convex polygon and tree of triangulations. Computational Geometry
1999; 13, 179-188.
- [8] Saračević M, Stanimirović P, Mašović S, Biševac E. Implementation of the convex polygon triangulation algorithm.
Facta Universitatis, Series Mathematics and Informatics 2012; 27, 213-228.
- [9] Stanimirović P, Krtolica P, Saračević M, Mašović S. Decomposition of Catalan numbers and convex polygon
triangulations. International Journal of Computer Mathematics 2014; 19, 1315-1328.
- [10] Saračević M, Stanimirović P, Krtolica P, Mašovič S. Construction and notation of convex polygon triangulation
based on ballot problem. Romanian Journal of Information Science and Technology 2014; 17, 237-251.
- [11] Sen-Gupta S, Mukhopadhyaya K, Bhattacharya BB, Sinha BP. Geometric classification of triangulations and their
enumeration in a convex polygon. Computers and Mathematics with Applications 1994; 27, 99-115.
- [12] Saračević M, Mašović S, Milošević D. JAVA Implementation for triangulation of convex polygon based on
Lukasiewicz algorithm and binary tree. Southeast Europe Journal of Soft Computing 2013; 2, 40-45.