This analysis reveals efficient convex polygon covering strategies using set cover, indicating significant improvements in computational approaches.
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.
No takes yet. Share an insight, caveat, or question.
Loïc Crombez (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: