2026-08-08T05:37:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17916 2024-03-06T11:00:42Z ddc:004 open_access

Constructing Concise Convex Covers via Clique Covers (CG Challenge) Abrahamsen, Mikkel Bille Meyling, William Nusser, André Convex cover Polygons with holes Algorithm engineering Vertex clique cover This work describes 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: (1) Create a suitable partition of P. (2) Compute a visibility graph of the pieces of the partition. (3) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikkel Abrahamsen and William Bille Meyling and André Nusser 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.66 urn:nbn:de:0030-drops-179164 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.66 eng https://creativecommons.org/licenses/by/4.0/legalcode