Constructing Concise Convex Covers via Clique Covers
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 1,87 MB, PDF-dokument
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.
| Originalsprog | Engelsk |
|---|---|
| Titel | 39th International Symposium on Computational Geometry, SoCG 2023 |
| Redaktører | Erin W. Chambers, Joachim Gudmundsson |
| Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Publikationsdato | 2023 |
| Sider | 1-9 |
| Artikelnummer | 66 |
| ISBN (Elektronisk) | 9783959772730 |
| DOI | |
| Status | Udgivet - 2023 |
| Begivenhed | 39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, USA Varighed: 12 jun. 2023 → 15 jun. 2023 |
Konference
| Konference | 39th International Symposium on Computational Geometry, SoCG 2023 |
|---|---|
| Land | USA |
| By | Dallas |
| Periode | 12/06/2023 → 15/06/2023 |
| Navn | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Vol/bind | 258 |
| ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Funding Mikkel Abrahamsen: Supported by Starting Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere Aude research career programme. Part of BARC, supported by the VILLUM Foundation grant 16582. William Bille Meyling: Supported by Starting Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere Aude research career programme. André Nusser: Part of BARC, supported by the VILLUM Foundation grant 16582.
Publisher Copyright:
© Mikkel Abrahamsen, William Bille Meyling, and André Nusser; licensed under Creative Commons License CC-BY 4.0.
ID: 384030473