Abstract
Let P be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in P. We say two points a,b∈P can see each other if the line segment seg(a,b) is contained in P. We denote by V(P) the family of all minimum guard placements. The Hausdorff distance makes V(P) a metric space and thus a topological space. We show homotopy-universality, that is, for every semi-algebraic set S there is a polygon P such that V(P) is homotopy equivalent to S. Furthermore, for various concrete topological spaces T, we describe instances I of the art gallery problem such that V(I) is homeomorphic to T.
| Original language | English |
|---|---|
| Pages (from-to) | 1092-1130 |
| Number of pages | 39 |
| Journal | Discrete and Computational Geometry |
| Volume | 71 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Apr 2024 |
Bibliographical note
Publisher Copyright:© The Author(s) 2023.
Funding
This research started at the 18th Gremo's Workshop on Open Problems (GWOP) in Morschach, Switzerland, 2021. We thank the organizers for providing a very pleasant and inspiring working atmosphere. Tillmann Miltzow is generously supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 016.Veni.192.250. Patrick Schnider has received funding from the European Research Council under the European Unions Seventh Framework Programme ERC Grant agreement ERC StG 716424 - CASe. We thank anonymous reviewers for their useful feedback.
| Funders | Funder number |
|---|---|
| Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 016 |
| Netherlands Organisation for Scientific Research (NWO) | ERC StG 716424 - CASe |
| European Research Council under the European Unions Seventh Framework Programme ERC |
Keywords
- 68Q25
- Art gallery problem
- Computational geometry
- Topological universality