LIPIcs.SoCG.2023.67.pdf
- Filesize: 0.93 MB
- 9 pages
Document
Shadoks Approach to Convex Covering (CG Challenge)
Author
Guilherme D. da Fonseca 
-
Part of:
Volume:
39th International Symposium on Computational Geometry (SoCG 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-06-09
File
Document Identifiers
Author Details
Acknowledgements
We would like to thank the Challenge organizers and other competitors for their time, feedback, and making this whole event possible. We would also like to thank the second year undergraduate students Rayis Berkat, Ian Bertin, Ulysse Holzinger, and Julien Jamme for coding a solution visualisation tool that allows you to view all our best solutions in https://pageperso.lis-lab.fr/guilherme.fonseca/cgshop23view/.
Cite As Get BibTex
Guilherme D. da Fonseca. Shadoks Approach to Convex Covering (CG Challenge). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 67:1-67:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.67
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Set cover
- covering
- polygons
- convexity
- heuristics
- enumeration
- simulated annealing
- integer programming
- computational geometry
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
Supplementary Materials
-
Software (Source Code)
https://github.com/gfonsecabr/shadoks-CGSHOP2023
browse
archived version
References
-
Mikkel Abrahamsen, William B. Meyling, and André Nusser. Constructing concise convex covers via clique covers. In 39th International Symposium on Computational Geometry (SoCG 2023), volume 258, pages 62:1-62-9, 2023.
-
Coen Bron and Joep Kerbosch. Algorithm 457: finding all cliques of an undirected graph. Communications of the ACM, 16(9):575-577, 1973.
-
Kyung-Yong Chwa, Byung-Cheol Jo, Christian Knauer, Esther Moet, René Van Oostrum, and Chan-Su Shin. Guarding art galleries by guarding witnesses. International Journal of Computational Geometry & Applications, 16(02n03):205-226, 2006.
-
IBM ILOG CPLEX. V22.1: User’s manual for CPLEX. International Business Machines Corporation, 2023.
- Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra. Minimum coverage by convex polygons: The CG:SHOP challenge 2023, 2023. URL: http://arxiv.org/abs/2303.07007.
-
Ina Koch. Enumerating all connected maximal common subgraphs in two graphs. Theoretical Computer Science, 250(1-2):1-30, 2001.
- O. Tange. Gnu parallel - the command-line power tool. ;login: The USENIX Magazine, 36(1):42-47, February 2011. URL: http://www.gnu.org/s/parallel.
- The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 5.5.1 edition, 2022. URL: https://doc.cgal.org/5.5.1/Manual/packages.html.