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.
| Original language | English |
|---|---|
| Title of host publication | 39th International Symposium on Computational Geometry, SoCG 2023 |
| Editors | Erin W. Chambers, Joachim Gudmundsson |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publication date | 2023 |
| Pages | 1-9 |
| Article number | 66 |
| ISBN (Electronic) | 9783959772730 |
| DOIs | |
| Publication status | Published - 2023 |
| Event | 39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, United States Duration: 12 Jun 2023 → 15 Jun 2023 |
Conference
| Conference | 39th International Symposium on Computational Geometry, SoCG 2023 |
|---|---|
| Country/Territory | United States |
| City | Dallas |
| Period | 12/06/2023 → 15/06/2023 |
| Series | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 258 |
| ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:© Mikkel Abrahamsen, William Bille Meyling, and André Nusser; licensed under Creative Commons License CC-BY 4.0.
Keywords
- Algorithm engineering
- Convex cover
- Polygons with holes
- Vertex clique cover