×
Mašović, Sead H.; Elshaarawy, Islam A.; Stanimirović, Predrag S.; Krtolica, Predrag V.

Orbiting triangle method for convex polygon triangulation. (English) Zbl 1488.68130

Appl. Anal. Discrete Math. 12, No. 2, 439-454 (2018).
Summary: 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.

Cited in 1 Document

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B55 Computational aspects related to convexity
52C45 Combinatorial complexity of geometric structures

Keywords:

convex polygon triangulation; Catalan triangle; Catalan numbers
Cite Review PDF
Full Text: DOI

References:

[1] A. Asinowski, C. Krattenthaler, T. Mansour: Counting triangulations of balanced subdivisions of convex polygons. Electronic Notes in Discrete Mathematics 54(2016), 73-78. · Zbl 1356.05006
[2] A. Asinowski, C. Krattenthaler, T. Mansour: Counting triangulations of some classes of subdivided convex polygons. European Journal of Combinatorics 62(2017), 92-114. · Zbl 1359.05006
[3] H. ElGindy, H. Everett, G. Toussaint: Slicing an ear using prune-and-search, Pattern Recognition Letters 14(1993), 719-722. · Zbl 0781.68114
[4] D.F. Bailey: Counting Arrangements of 1’s and -1’s. Mathematics Magazine, 69 (1996), 128-131. · Zbl 0859.05007
[5] F. Hurtado and M. Noy: Ears of triangulations and Catalan numbers. Discrete Mathematics, 149(1996), 319-324. · Zbl 0844.68118
[6] F. Hurtado and M. Noy: Graph of triangulations of a convex polygon and tree of triangulations. Computational Geometry, 13(1999), 179-188. · Zbl 0948.68127
[7] F. Hurtado, M. Noy: Counting triangulations of almost-convex polygons. Ars Com-binatoria 45(1997), 169-179. · Zbl 0933.05001
[8] I. Kanj, E. Sedgwick, G. Xia: Computing the flip distance between triangulations. Discrete Compu. Geom. 58(2017), 313-344. · Zbl 1371.05063
[9] J. M. Keil, T. S. Vassilev: Algorithms for optimal area triangulations of a convex polygon. Computational Geometry 35(2006), 173-187. · Zbl 1102.65026
[10] G.T. Klincsek: Minimal triangulations of polygonal domains. Annals of Discrete Mathematics 9(1980), 121-123. · Zbl 0452.05002
[11] M. Korman, S,. Langerman, W. Mulzer, A. Pilz, M. Saumell, B. Vogten-huber: The dual diameter of triangulations. Computational Geometry: Theory and Applications 68(2018), 243-252. · Zbl 1380.05049
[12] T. Koshy: Catalan Numbers with Applications. Oxford University Press, London, UK (2009) . · Zbl 1159.05001
[13] P. Krtolica, P. Stanimirović, M. Tasić and S. Pepić: Triangulation of Convex Polygon with Storage Support. Facta Universitatis, Series: Mathematics and Informat-ics, 29(2)(2014), 189-208. · Zbl 1349.68296
[14] S. Negami: Diagonal flips in triangulations of surfaces. Discrete Mathematics 135(1994), 225-232. · Zbl 0823.05028
[15] J. O’Rourke: Art gallery theorems and algorithms. Oxford Univ. Press, Oxford (1987). · Zbl 0653.52001
[16] M. Saračević, P.S. Stanimirović, S. Mašović and E. Biševac: Implementation of the convex polygon triangulation algorithm. Facta Universitatis, Series: Mathematics and Informatics, 27(2012), 213-228. · Zbl 1299.68197
[17] M. Saračević, P.S. Stanimirović, P. Krtolica and S. Mašović: Construction and notation of convex polygon triangulation based on ballot problem. Romanian Journal of Information Science and Technology, 17(2014), 237-251.
[18] L.W. Shapiro: A Catalan triangle. Discrete Mathematics, 14(1976), 83-90. · Zbl 0323.05004
[19] P.S. Stanimirović, P. Krtolica, M. Saračević and S. Mašović: Block Method for Convex Polygon Triangulation. Romanian Journal of Information Science and Tech-nology, 15(4)(2012), 344-354.
[20] P.S. Stanimirović, P. Krtolica, M. Saračević and S. Mašović: Decomposi-tion of Catalan numbers and convex polygon triangulations. International Journal of Computer Mathematics, 91(2014), 1315-1328. · Zbl 1302.52003
[21] J. Yu, Z.-Li Tang: Generating strictly binary trees at random based on convex poly-gon triangulations. International Journal Of Computer Mathematics 93(2016), 445-452. · Zbl 1338.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.