LIPIcs.SoCG.2023.66.pdf
- Filesize: 1.87 MB
- 9 pages
Document
Constructing Concise Convex Covers via Clique Covers (CG Challenge)
Authors
Mikkel Abrahamsen 
,
André Nusser
-
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 want to thank the CG:SHOP 2023 organizers and the other participants (especially Guilherme Dias da Fonseca) for creating such a fun challenge and for helpful comments on our write-up. We also want to thank Martin Aumüller and Rasmus Pagh for access and help with using their server. Finally, we want to thank Darren Strash for quick and last-minute support using the ReduVCC implementation.
Cite As Get BibTex
Mikkel Abrahamsen, William Bille Meyling, and André Nusser. Constructing Concise Convex Covers via Clique Covers (CG Challenge). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 66:1-66:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.66
Abstract
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
- Mathematics of computing → Combinatorial algorithms
Keywords
- Convex cover
- Polygons with holes
- Algorithm engineering
- Vertex clique cover
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
Supplementary Materials
-
Software
https://github.com/willthbill/ExtensionCC
browse
archived version
- Text (Thesis) https://github.com/willthbill/ExtensionCC/blob/main/bachelorthesis.pdf
References
- Mikkel Abrahamsen. Covering polygons is even harder. In Symposium on Foundations of Computer Science (FOCS), pages 375-386, 2021. URL: https://doi.org/10.1109/FOCS52979.2021.00045.
- David Chalupa. Construction of near-optimal vertex clique covering for real-world networks. Comput. Informatics, 34(6):1397-1417, 2015. URL: http://www.cai.sk/ojs/index.php/cai/article/view/1276.
- Joseph C. Culberson and Robert A. Reckhow. Covering polygons is hard. J. Algorithms, 17(1):2-44, 1994. URL: https://doi.org/10.1006/jagm.1994.1025.
- Guilherme D. da Fonseca. Shadoks approach to convex covering. In Symposium on Computational Geometry (SoCG), volume 258, 2023. URL: https://pageperso.lis-lab.fr/guilherme.fonseca/CGSHOP23conf.pdf.
- Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, and Stefan Schirra. Minimum coverage by convex polygons: The CG:SHOP Challenge 2023, 2023. URL: https://arxiv.org/abs/2303.07007.
- Michael Hemmer, Kan Huang, Francisc Bungiu, and Ning Xu. 2D visibility computation. In CGAL User and Reference Manual. CGAL Editorial Board, 5.5.2 edition, 2023. URL: https://doc.cgal.org/5.5.2/Manual/packages.html#PkgVisibility2.
- Susan Hert and Stefan Schirra. 2D convex hulls and extreme points. In CGAL User and Reference Manual. CGAL Editorial Board, 5.5.2 edition, 2023. URL: https://doc.cgal.org/5.5.2/Manual/packages.html#PkgConvexHull2.
- Darren Strash and Louise Thompson. Effective data reduction for the vertex clique cover problem. In Symposium on Algorithm Engineering and Experiments (ALENEX), pages 41-53, 2022. URL: https://doi.org/10.1137/1.9781611977042.4.
- The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 5.5.2 edition, 2023. URL: https://doc.cgal.org/5.5.2/Manual/packages.html.
- Mariette Yvinec. 2D triangulations. In CGAL User and Reference Manual. CGAL Editorial Board, 5.5.2 edition, 2023. URL: https://doc.cgal.org/5.5.2/Manual/packages.html#PkgTriangulation2.