Memoization method for storing of minimum-weight triangulation of a convex polygon

• Autorzy: Selimi Aybeyan , Krrabaj Samedin , Saracevic Muzafer , Pepić Selver

Identyfikatory

DOI

10.7494/csci.2019.20.2.3193

• Języki publikacji: EN

Abstrakty

EN

This study presents a practical view of dynamic programming, specifically in the context of the application of finding the optimal solutions for the polygon triangulation problem. The problem of the optimal triangulation of polygon is considered to be as a recursive substructure. The basic idea of the constructed method lies in finding to an adequate way for a rapid generation of optimal triangulations and storing - them in as small as possible memory space. The upgraded method is based on a memoization technique, and its emphasis is in storing the results of the calculated values and returning the cached result when the same values again occur. The significance of the method is in the generation of the optimal triangulation for a large number of n. All the calculated weights in the triangulation process are stored and performed in the same table. Results processing and implementation of the method was carried out in the Java environment and the experimental results were compared with the square matrix and Hurtado-Noy method.

Słowa kluczowe

EN

minimum-weight triangulation; catalan number; data storage; memoization; dynamic programming

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2019
• Tom: Vol. 20 (2)
• Strony: 195--211
• Opis fizyczny: Bibliogr. 21 poz., rys., tab.

Twórcy

autor

Selimi Aybeyan

• International Vision University, Faculty of Informatics, Gostivar

autor

Krrabaj Samedin

• University of Prizren, Faculty of Computer Science

autor

Saracevic Muzafer

• University of Novi Pazar, Department of Computer Science

autor

Pepić Selver

• Educons University, Department of Computer Science, Novi Sad

Bibliografia

• [1] Attene M., Campen M., Kobbelt L.: Polygon Mesh Repairing: An Application Perspective, ACM Computing Surveys, vol. 45, pp. 1-33, 2013.
• [2] Barequet G., Dickerson M., Eppstein D.: On triangulating three-dimensional polygons. In: Proceedings of the twelfth annual symposium on Computational geometry, SCG`96, ACM, pp. 38-47, 1996.
• [3] Barequet G., Sharir M.: Filling gaps in the boundary of a polyhedron, Computer Aided Geometry Design, vol.12, pp. 207-229, 1995.
• [4] Batty C., Xenos S., Houston B.: Tetrahedral Embedded Boundary Methods for Accurate and Flexible Adaptive Fluids, Computer Graphics Forum (Eurographics), vol. 29, pp. 695-704, 2010.
• [5] Bessmeltsev M., Wang C., Sheffer A., Singh K.: Design-Driven Quadrangulation of Closed 3d Curves, VACM Transactions on Graphics, SigGraph Asia, vol. 31(5), 2012.
• [6] Chazelle B.: Triangulating a Simple Polygon in Linear Time, Discrete Computational Geometry, vol. 6, pp. 485-524, 1991.
• [7] Cormen T.H., Leiserson C.E., Rivest R.L., Clifford S.: Introduction to Algorithms, Third Edition, MIT Press, 2009.
• [8] Gilbert P.D.: New results in planar triangulations, Technical report, Urbana, Illinois: Coordinated Science Laboratory, University of Illinois, 1979.
• [9] de Goes F., Breeden K., Ostromoukhov V., Desbrun M.: Blue Noise Through Optimal Transport, ACM Transactions on Graphics, vol. 31(6), pp. 1-11, 2012.
• [10] Jin M., Kim J., Luo F., Gu X.: Discrete surface ricci flow, IEEE Transactions on Visualization and Computer Graphics, vol. 14(5), pp. 1030-1043, 2008.
• [11] Kenneth R., Sheffer A., Wither J., Cani M.P., Thibert B.: Developable Surfaces from Arbitrary Sketched Boundaries, Proceedings of Eurographics Symposium on Geometry Process, 2007.
• [12] Klincsek G.T.: Minimal Triangulations of Polygonal Domains, Combinatorics 79, Annals of Discrete Mathematics, vol. 9, Elsevier, 1980.
• [13] Liu L., Bajaj C., Deasy J., Low D.A., Ju T.: Surface Reconstruction from Non-Parallel Curve Networks, Computer Graphics Forum, vol. 27(2), pp. 155-163, 2008.
• [14] Masovic S., Saracevic M.: Finding optimal triangulation based on block method, Southeast Europe Journal of Soft Computing, vol. 3(2), pp. 14-18, 2014.
• [15] Mercat C.: Discrete Riemann surfaces and the Ising model, Communications in Mathematical Physics, vol. 218, pp. 177-216, 2001.
• [16] Roth G., Wibowoo E.: An Efficient Volumetric Method for Building Closed Triangular Meshes from 3-D Image and Point Data. In: Proceedings of the Conference on Graphics Interface'97, Canadian Information Processing Society, pp. 173-180, 1997.
• [17] Saracevic M., Masovic S., Stanimirovic P., Krtolica P.: Method for finding and storing optimal triangulations based on square matrix, Applied Sciences Electronic Journal, vol. 20, pp. 167-180, 2018.
• [18] Saracevic M., Selimi A.: Convex polygon triangulation based on planted trivalent binary tree and ballot problem, Turkish Journal of Electrical Engineering and Computer Sciences, vol. 27(1), pp. 346-361, 2019.
• [19] Seidel R.: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, Computational Geometry, vol. 1, pp. 51-64, 1991.
• [20] Selimi A., Saracevic M.: Computational geometry applications, Southeast Europe Journal of Soft Computing, vol. 7(2), pp. 8-15, 2018.
• [21] Stanimirovic P.S., Krtolica P.V., Saracevic M.H., Masovic S.H.: Block Method for Convex Polygon Triangulation, Romanian Journal of Information Science and Technology, vol. 15(4), pp. 344-354, 2012