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 trivalent binary tree and ballot notation. The properties of the Catalan numbers were examined and their decomposition and application in developing the hierarchy and triangulation trees were analyzed. The method of storage and processing of triangulation was constructed on the basis of movements through the polygon. This method was derived from vertices and leaves of the planted trivalent binary tree. The research subject of the paper is analysis and comparison of a constructed method for solving of convex polygon triangulation problem with other methods and generating graphical representation. The application code of the algorithms was done in the Java programming language.

___

  • Koshy T. Catalan Numbers with Applications. New York, NY, USA: Oxford University Press,2009.
  • Even S. Graph Algorithms. New York, NY, USA: Cambridge University Press, 2011.
  • Goodman JE, O’Rourke J. Handbook of Discrete and Computational Geometry. New York, NY, USA: Chapman and Hall and CRC Press, 2004.
  • O’Rourke J. Computational Geometry in C. 2nd ed. Cambridge, UK: Cambridge University Press, 1997.
  • Preparata F, Shamos MI. Computational Geometry: An introduction. Berlin, Germany: Springer-Verlag, 1985.
  • Koshy T. Discrete Mathematics with Applications. Burlington, MA, USA: Elsevier Academic Press, 2004.
  • Hurtado F, Noy M. Graph of triangulations of a convex polygon and tree of triangulations. Computational Geometry 1999; 13, 179-188.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.