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

Abstract

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.