Shadoks Approach to Convex Covering

03/14/2023
by   Guilherme D. da Fonseca, et al.
0

We describe the heuristics used by the Shadoks team in the CG:SHOP 2023 Challenge. The Challenge consists of 206 instances, each being a polygon with holes. The goal is to cover each instance polygon with a small number of convex polygons. Our general strategy is the following. We find a big collection of large (often maximal) convex polygons inside the instance polygon and then solve several set cover problems to find a small subset of the collection that covers the whole polygon.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset