Standard
Constructing Concise Convex Covers via Clique Covers. / Abrahamsen, Mikkel; Meyling, William Bille; Nusser, André.
39th International Symposium on Computational Geometry, SoCG 2023. ed. / Erin W. Chambers; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. p. 1-9 66 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 258).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Abrahamsen, M, Meyling, WB & Nusser, A 2023,
Constructing Concise Convex Covers via Clique Covers. in EW Chambers & J Gudmundsson (eds),
39th International Symposium on Computational Geometry, SoCG 2023., 66, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 258, pp. 1-9, 39th International Symposium on Computational Geometry, SoCG 2023, Dallas, United States,
12/06/2023.
https://doi.org/10.4230/LIPIcs.SoCG.2023.66
APA
Abrahamsen, M., Meyling, W. B., & Nusser, A. (2023).
Constructing Concise Convex Covers via Clique Covers. In E. W. Chambers, & J. Gudmundsson (Eds.),
39th International Symposium on Computational Geometry, SoCG 2023 (pp. 1-9). [66] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 258
https://doi.org/10.4230/LIPIcs.SoCG.2023.66
Vancouver
Abrahamsen M, Meyling WB, Nusser A.
Constructing Concise Convex Covers via Clique Covers. In Chambers EW, Gudmundsson J, editors, 39th International Symposium on Computational Geometry, SoCG 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. p. 1-9. 66. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 258).
https://doi.org/10.4230/LIPIcs.SoCG.2023.66
Author
Abrahamsen, Mikkel ; Meyling, William Bille ; Nusser, André. / Constructing Concise Convex Covers via Clique Covers. 39th International Symposium on Computational Geometry, SoCG 2023. editor / Erin W. Chambers ; Joachim Gudmundsson. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. pp. 1-9 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 258).
Bibtex
@inproceedings{dd0a90e74f3045b2a0069cc7388e43a2,
title = "Constructing Concise Convex Covers via Clique Covers",
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.",
keywords = "Algorithm engineering, Convex cover, Polygons with holes, Vertex clique cover",
author = "Mikkel Abrahamsen and Meyling, {William Bille} and Andr{\'e} Nusser",
note = "Publisher Copyright: {\textcopyright} Mikkel Abrahamsen, William Bille Meyling, and Andr{\'e} Nusser; licensed under Creative Commons License CC-BY 4.0.; 39th International Symposium on Computational Geometry, SoCG 2023 ; Conference date: 12-06-2023 Through 15-06-2023",
year = "2023",
doi = "10.4230/LIPIcs.SoCG.2023.66",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "1--9",
editor = "Chambers, {Erin W.} and Joachim Gudmundsson",
booktitle = "39th International Symposium on Computational Geometry, SoCG 2023",
}
RIS
TY - GEN
T1 - Constructing Concise Convex Covers via Clique Covers
AU - Abrahamsen, Mikkel
AU - Meyling, William Bille
AU - Nusser, André
N1 - Publisher Copyright:
© Mikkel Abrahamsen, William Bille Meyling, and André Nusser; licensed under Creative Commons License CC-BY 4.0.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
KW - Algorithm engineering
KW - Convex cover
KW - Polygons with holes
KW - Vertex clique cover
U2 - 10.4230/LIPIcs.SoCG.2023.66
DO - 10.4230/LIPIcs.SoCG.2023.66
M3 - Article in proceedings
AN - SCOPUS:85163519284
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 9
BT - 39th International Symposium on Computational Geometry, SoCG 2023
A2 - Chambers, Erin W.
A2 - Gudmundsson, Joachim
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 39th International Symposium on Computational Geometry, SoCG 2023
Y2 - 12 June 2023 through 15 June 2023
ER -
