Topological Art in Simple Galleries
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Topological Art in Simple Galleries. / Bertschinger, Daniel; El Maalouly, Nicolas ; Miltzow, Tillmann; Schnider, Patrick; Weber, Simon .
Proceedings - 5fh Symposium on Simplicity in Algorithms (SOSA). SIAM, 2022. p. 87 - 116.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Topological Art in Simple Galleries
AU - Bertschinger, Daniel
AU - El Maalouly, Nicolas
AU - Miltzow, Tillmann
AU - Schnider, Patrick
AU - Weber, Simon
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
U2 - 10.1137/1.9781611977066.8
DO - 10.1137/1.9781611977066.8
M3 - Article in proceedings
SP - 87
EP - 116
BT - Proceedings - 5fh Symposium on Simplicity in Algorithms (SOSA)
PB - SIAM
T2 - 5th Symposium on Simplicity in Algorithms (SOSA 2022)
Y2 - 10 January 2022 through 11 January 2022
ER -
ID: 343299274