2023/03/14 by da Fonseca, Guilherme D.
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2303.07696
In the convex covering problem, we are given a convex polygon with holes P and the goal is to cover P using a small number of convex polygons that lie inside P. In this paper, we solve the problem using the following strategy. We find a big collection of large (often maximal) convex polygons inside P and then solve several set cover problems to find a small subset of the collection that covers the whole polygon. The quality of our heuristics is confirmed by winning the second place in the CG:SHOP 2023 Challenge.