We describe a practical method to find near-optimal solutions for the area-optimal simple polygonization problem: Given a set \(S\) of \(n\) points in the plane, compute a simple polygonalization of \(S\) (a simple polygon the vertex set of which is precisely the set \(S\)) that has maximum or minimum area among all polygonalizations of \(S\). (Every set \(S\) of \(n\) points in the plane has at least one polygonalization. The number of different polygonalizations is finite, though possibly exponentially large, for any finite points set \(S\).) The optimization problems, both for maximization or for minimization, are known to be NP-hard. Our solution consists of two phases. At the first phase we generate a valid polygon that passes through all the points of the input set. At the second phase we use simulated annealing, which converges to a near-optimal solution through a sequence of iterations. Every iteration starts with a valid polygon and ends with a valid polygon, typically with better area property (either larger or smaller, depending on the optimization objective). We use several tools in computational geometry to implement the transitions, such as KD-trees and constrained triangulations to implement the transition methods. We discard invalid polygons that may result while applying the transition. These transitions are divided into local steps, which alter the order of vertices of a small chain of the current polygon, and global steps, applied on random vertices. The validity of polygons resulting from applying local steps can be quickly tested. However, the gain in the area property is small. On the other hand, testing the validity of polygons resulting from applying global steps is much more time consuming, but the gain in the area property is much larger.
The problem above was presented as a challenge at SoCG 20; see https://sites.google.com/stonybrook.edu/cgweek2019-workshop/. Our team was awarded 3rd place.