The "Divide and Conquer" technique to solve the Minimum Area Polygonalization problem
Maksym Osiponok, Vasyl Tereshchenko · 2019 IEEE International Conference on Advanced Trends in Information Theory (ATIT) · 2019
We consider an application of the divide and conquer technique to the Minimum Area Polygonalization (MAP) problem. It is known that MAP problem belongs to NPHard set of problems. In this paper we propose a heuristic algorithm for solving the Minimum Area Polygonalization problem that is based on recursive subdivision of the set of points into two smaller subsets, constructing approximated solutions for the subsets and merging them with respect to minimizing the total area using the minimum area quadrilateral between two polygons. The algorithm of finding such a quadrilateral is described at this paper as well. Time complexity of the entire algorithm is O (n2) using O(n) memory.