Constructing Concise Convex Covers via Clique Covers

This work is the full version describing the winning implementation of the CG:SHOP 2023 Challenge. The topic of the Challenge was the convex cover problem: given a polygon P (with holes), find a minimum-cardinality set of convex polygons whose union equals P. We use a three-step approach: • Create a suitable triangulation of P. • Compute a visibility graph of the triangles. • Solve a vertex clique cover problem on the visibility graph, from which we then derive the convex cover. This way we capture the geometric difficulty in the first step and the combinatorial difficulty in the third step.