2026-07-23T07:44:35Z https://drops.dagstuhl.de/oai

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

Shadoks Approach to Convex Covering (CG Challenge) da Fonseca, Guilherme D. Set cover covering polygons convexity heuristics enumeration simulated annealing integer programming computational geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guilherme D. da Fonseca 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.67 urn:nbn:de:0030-drops-179178 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.67 eng https://creativecommons.org/licenses/by/4.0/legalcode