Exact and Heuristic Algorithms for Convex Polygon Decomposition

Convex decomposition plays a central role in computational geometry and is a key preprocessing step in applications such as robotic motion planning, 2D packing, pattern recognition, and manufacturing. This work revisits the minimum convex decomposition problem and proposes both an exact mathematical model and an efficient heuristic algorithm capable of handling simple polygons as well as polygons with holes. The methodology incorporates a visibility-preserving bridge transformation that converts holed polygons into equivalent simple instances, enabling the extension of classical decomposition schemes to more general topologies. In addition, a convex-union post-processing phase is implemented to reduce the number of convex parts obtained by either method. The performance of the proposed approach is evaluated on benchmark instances from the literature and on a new dataset of polygons with holes introduced in this work. The exact model consistently produces optimal decompositions for small and medium instances, while the heuristic achieves near-optimal solutions with significantly reduced computation times. The union phase further decreases the number of resulting convex pieces in most cases. All codes, datasets, and results are publicly released to facilitate reproducibility and comparison with future methods.