Open AccessOrbiting triangle method for convex polygon triangulation
Author(s) -
H Sead Masovic,
Islam A. Elshaarawy,
Stefan Stanimirović,
Predrag V. Krtolica
Publication year - 2018
Publication title -
applicable analysis and discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.69
H-Index - 26
eISSN - 2406-100X
pISSN - 1452-8630
DOI - 10.2298/aadm170829013m
Subject(s) - polygon (computer graphics) , regular polygon , convex polygon , mathematics , triangulation , polygon covering , combinatorics , minimum weight triangulation , set (abstract data type) , point set triangulation , algorithm , computer science , delaunay triangulation , bowyer–watson algorithm , geometry , telecommunications , frame (networking) , programming language
Finding all possible triangulations of convex polygon is a highly time and memory space consuming combinatorial problem. Therefore, it is very important to develop algorithms for generating triangulations as efficiently as possible. This paper presents a new method for generating triangulations of a convex polygon, called Orbiting triangle method (OTM). The method is based on using the set of (n-1)-gon triangulations during the set of n-gon triangulations creation. The main feature of the OTM algorithm is the use of the Catalan triangle to identify valid triangulations, so that the algorithm spends almost no time to eliminate duplicates. In this way, the method possesses small complexity and saves the computational time required for detecting and eliminating duplicates.