Topological Art in Simple Galleries

Research output: Contribution to journalJournal articleResearchpeer-review

Documents

  • Fulltext

    Final published version, 1.05 MB, PDF document

  • 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.

Original languageEnglish
JournalDiscrete and Computational Geometry
Volume71
Pages (from-to)1092–1130
ISSN0179-5376
DOIs
Publication statusPublished - 2024

Bibliographical note

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

    Research areas

  • Art gallery problem, Computational geometry, Topological universality

ID: 369291347