Topological Art in Simple Galleries

METADATA ONLY

Author / Producer

Bertschinger, Daniel El Maalouly, Nicolas Miltzow, Tillmann

Date

2022

Publication Type

Conference Paper

ETH Bibliography

yes

Citations

Altmetric
METADATA ONLY

Data

Rights / License

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.

Permanent link

http://hdl.handle.net/20.500.11850/593035

Publication status

published

External links

https://doi.org/10.1137/1.9781611977066.8 north_east

Editor

Bringmann, Karl north_east Chan, Timothy north_east

Book title

Symposium on Simplicity in Algorithms (SOSA)

Journal / series

Volume

Pages / Article No.

87 - 116

Publisher

SIAM

Event

5th Symposium on Simplicity in Algorithms (SOSA 2022)

Edition / version

Methods

Software

Geographic location

Date collected

Date created

Subject

Organisational unit

03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus) check_circle

Notes

Funding

Related publications and datasets

Is previous version of:

More

Show all metadata