Robust guarding of polyomino shapes with movable guards
Restless Guards: Robust Guarding of Polyominoes
Computational GeometryData Structures and Algorithms
Summary
The paper looks at how to place security guards on a grid-like shape to watch the whole area even when guards can move a little bit from their spot. The authors study this for shapes made of square cells and where guards see in straight lines through rows or columns. They find that allowing small movements helps in covering shapes fully for certain movement limits but not always for larger ones. They also provide methods to find the minimum number of guards needed and show when this is hard to compute. For simpler shapes without holes, they give efficient solutions and approximations.
What this means in practice
- •For security system designers: Plan guard placements in grid-like floor plans while allowing small movement for each guard to ensure coverage despite position uncertainty.
- •For robot control engineers: Design patrol routes for mobile robots that cover polygonal regions with movement limits and visibility constraints.
Authors
Linda Kleist, Ramin Kosfeld, Christian Rieck
Abstract
The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants. In this work, we investigate a setting in which full coverage of the gallery shall be ensured despite locational uncertainty of the guards. We study this problem for polyominoes under rectangular visibility, where a $k$-restless guard assigned to a cell may move to any cell within distance at most $k$. While all polyominoes are guardable for $k\in\{0, 1\}$, the same is not true for all $k\geq 2$. However, for a given polyomino $P$ and integer $k$, we present an algorithm that identifies a $k$-restless guard set of $P$ in polynomial time, or decides that no such set exists. For the cases $k\in\{0,1\}$, where $k$-restless guard sets always exist, we provide tight worst-case bounds on the number of $k$-restless guards that are always sufficient and sometimes necessary to guard a hole-free polyomino with $n$ vertices or $m$ cells. Moreover, we show that computing a minimum guard set is NP-hard. Complementing the hardness, we provide polynomial-time algorithms for solving the problem optimally for histograms, and leverage this to obtain a $20k$-approximation for polyominoes without holes.