Topological Art in Simple Galleries

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 1,05 MB, PDF-dokument

  • Daniel Bertschinger
  • Nicolas El Maalouly
  • Tillmann Miltzow
  • Patrick Schnider
  • Simon Weber

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.

OriginalsprogEngelsk
TidsskriftDiscrete and Computational Geometry
Vol/bind71
Sider (fra-til)1092–1130
ISSN0179-5376
DOI
StatusUdgivet - 2024

Bibliografisk note

Funding Information:
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.

Publisher Copyright:
© 2023, The Author(s).

ID: 369291347