Constructing Concise Convex Covers via Clique Covers

Mikkel Abrahamsen*, William Bille Meyling, André Nusser

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

1 Citation (Scopus)
17 Downloads (Pure)

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 languageEnglish
Title of host publication39th International Symposium on Computational Geometry, SoCG 2023
EditorsErin W. Chambers, Joachim Gudmundsson
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date2023
Pages1-9
Article number66
ISBN (Electronic)9783959772730
DOIs
Publication statusPublished - 2023
Event39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, United States
Duration: 12 Jun 202315 Jun 2023

Conference

Conference39th International Symposium on Computational Geometry, SoCG 2023
Country/TerritoryUnited States
CityDallas
Period12/06/202315/06/2023
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume258
ISSN1868-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

Cite this