Convex Covering Using Collections of Convex Polygons and Set Cover
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909652666548224 |
|---|---|
| author | da Fonseca, Guilherme D. |
| author_facet | da Fonseca, Guilherme D. |
| contents | In the convex covering problem, we are given a convex polygon with holes $P$ and the goal is to cover $P$ using a small number of convex polygons that lie inside $P$. In this paper, we solve the problem using the following strategy. We find a big collection of large (often maximal) convex polygons inside $P$ and then solve several set cover problems to find a small subset of the collection that covers the whole polygon. The quality of our heuristics is confirmed by winning the second place in the CG:SHOP 2023 Challenge. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_07696 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Convex Covering Using Collections of Convex Polygons and Set Cover da Fonseca, Guilherme D. Computational Geometry In the convex covering problem, we are given a convex polygon with holes $P$ and the goal is to cover $P$ using a small number of convex polygons that lie inside $P$. In this paper, we solve the problem using the following strategy. We find a big collection of large (often maximal) convex polygons inside $P$ and then solve several set cover problems to find a small subset of the collection that covers the whole polygon. The quality of our heuristics is confirmed by winning the second place in the CG:SHOP 2023 Challenge. |
| title | Convex Covering Using Collections of Convex Polygons and Set Cover |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2303.07696 |