Triangle-Based Heuristics for Area Optimal Polygonizations
Natanael Ramos, Raí Caetano de Jesus, Pedro J. de Rezende, Cid C. de Souza, Fbio L. Usberti · ACM Journal of Experimental Algorithmics · 2022
In this article, we describe an empirical study conducted on problems of Polygonizations with Optimal Area: given a set \( S \) of points in the plane, find a simple polygon with minimum (Min-Area) or maximum (Max-Area) area whose vertices are all the points of \( S \) . Both problems arise in the context of pattern recognition, image reconstruction, and clustering. Higher dimensional variants play a role in object modeling, as well as optimal surface design. BothMin-AreaandMax-Areaare in NP-hard, and heuristics as well as exact methods have already been proposed. Our main contributions include the design and implementation of novel constructive heuristics and local search procedures to improve the solutions obtained by the former methods for the two problems.