Provably Good Algorithms for Guarding Problems
We study visibility based problems—specifically those, where several stationary or mobile guards need to monitor each point of a domain. These problems play a larger role in an increasing number of applications (e.g., surveillance, illumination and domain covering, and also in manufacturing) and are known to be computationally hard to solve in general. Hence, finding efficient ways to approximate them is important. We consider restricted polygonal domains with the goal to obtain efficient optimal solutions or better approximate solutions than those known for simple polygons. Also we will study k-transmitters: modems that can connect to “see” another device that is obstructed by at most k walls. If all points of an environment need to frequently connect to a k-transmitter, we want to find the shortest tour for the transmitter that allows for these connections. We focus on the design and analysis of algorithms and study the problems' computational complexity; their basic geometric properties, structures and worst-case combinatorial bounds provide insights on the construction of solutions.
Rahmat Ghasemi, Alireza Bagheri, Anna Brötzner, Faezah Farivar, Fatemeh Keshavarz-Kohjerdi, Bengt J. Nilsson, Christiane Schmidt:
m-Watchmen's Routes in Minbar and Generalized Minbar Polygons,
In Computational Geometry: Theory and Applications, Volume 131, March 2026, 102217
[doi]
Martin Balko, Anna Brötzner, Fabian Klute, Josef Tkadlec:
Faces in rectilinear drawings of complete graphs,
In European Journal of Combinatorics, Volume 130, December 2025, 104217
[doi]
Oswin Aichholzer, Anna Brötzner, Daniel Perz, Patrick Schnider:
Flips in odd matchings,
In Computational Geometry: Theory and Applications, Volume 129, December 2025, 102184
[doi]
Anna Brötzner, Bengt J. Nilsson, Christiane Schmidt:
Multiple Watchman Routes in Staircase Polygons,
In the 37th Canadian Conference on Computational Geometry (CCCG 2025)
[Preprint on arXiv]
Anna Brötzner, Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada:
Crossing and Independent Families among Polygons,
In the Algorithms and Data Structures Symposium (WADS) 2025
Anna Brötzner, Omrit Filtser,
Bengt J. Nilsson,
Christian Rieck, Christiane Schmidt:
Segment Watchman Routes,
In EuroCG 2025
[PDF], [Slides]
Anna Brötzner, Bengt J. Nilsson, Christiane Schmidt:
Two Watchmen's Routes in Staircase Polygons,
In EuroCG 2025
[PDF]
Omrit Filtser,
Erik Krohn, Bengt J. Nilsson,
Christian Rieck, Christiane Schmidt:
Guarding Polyominoes Under k-Hop Visibility,
In Algorithmica
[open access PDF at publisher], [doi],
[Preprint on arXiv], [Slides for a longer talk on the paper, prepared for a seminar with an introduction for a more general CS audience]
Recording of a seminar talk on this:
Anna Brötzner: Visibility in Graphs and Polygons, licentiate thesis, Malmö University, 2024
S. Fekete,
J. S.B. Mitchell,
C. Rieck,
C. Scheffer,
Christiane Schmidt:
Dispersive Vertex Guarding for Simple and Non-Simple Polygons,
In 36th Canadian Conference on Computational Geometry (CCCG 2024)
[Preprint on arXiv], [PDF of Proceedings]
Anna Brötzner, Bengt J. Nilsson, Christiane Schmidt:
The k-Transmitter Watchman Route Problem is
NP-Complete Even in Histograms and Star-Shaped
Polygons,
In 40th European Workshop on Computational Geometry (EuroCG)
[PDF]
Carlos Alegría , Anna Brötzner, BengtJ. Nilsson, Christiane Schmidt, Carlos Seara :
The Complexity of the Lower Envelope of
Collections of Various Geometric Shapes,
In 40th European Workshop on Computational Geometry (EuroCG)
[PDF]
O. Filtser,
E. Krohn, B.J. Nilsson,
C. Rieck, Christiane Schmidt:
Guarding Polyominoes under k-Hop Visibility,
In LATIN (Latin American Theoretical Informatics) 2024
[Preprint on arXiv], [Springer Link], [Slides for a longer talk on the paper, prepared for a seminar with an introduction for a more general CS audience]
Recording of a seminar talk on this:
Alireza Bagheri, Anna Brötzner, Faezah Farivar, Rahmat Ghasemi, Fatemeh Keshavarz-Kohjerdi, Erik Krohn, Bengt J. Nilsson, Christiane Schmidt:
Minsum m watchmen’s routes in Stiegl polygons,
In XX Spanish Meeting on Computational Geometry
[Booklet of abstracts], [PDF]
BengtJ. Nilsson, Christiane Schmidt:
k-Transmitter Watchman Routes,
In WALCOM 2023
[Preprint on arXiv], [Springer Link]
Talk about the problem at NYU's geometry seminar from December 2022
Erik Krohn, Bengt J. Nilsson, Christiane Schmidt:
Opposing Half Guards,
In CCCG 2022
[Preprint on arXiv], [PDF of Proceedings]
Bengt J. Nilsson, Christiane Schmidt:
k-Transmitter Watchman Routes,
In EuroCG 2022
[PDF of booklet of abstracts]