Guarding a polygon with few guards is an old and well-studied problem in computational
geometry. Here we consider the following variant: We assume that the polygon is orthogonal …

The chromatic orthogonal art gallery problem is a well-known problem in the computational
geometry. Two points in an orthogonal polygon P see each other if there is an axis-aligned …

We explore the art gallery problem for the special case that the domain (gallery) P is an m-
polyomino, a polyform whose cells are m unit squares. We study the combinatorics of …

An orthogonal polygon of P is called “thin” if the dual graph of the partition obtained by
extending all edges of P towards its interior until they hit the boundary is a tree. We show …

Abstract We study the Art Gallery Problem under k-hop visibility in polyominoes. In this
visibility model, two unit squares of a polyomino can see each other if and only if the shortest …

We study the art gallery problem when the instance is a polyomino, which is the union of
connected unit squares. It is shown that locating the minimum number of guards with r …

We consider a generalization of the classical Art Gallery Problem, where instead of a light
source, the guards, called k-transmitters, model a wireless device with a signal that can pass …

Given a graph $ G $, the $ k $-hop dominating set problem asks for a vertex subset $ D_k $
such that every vertex of $ G $ is in distance at most $ k $ to some vertex in $ D_k …

We introduce a new variant of the art gallery problem that comes from safety issues. In this
variant we are not interested in guard sets of smallest cardinality, but in guard sets with …

How many chess rooks or queens does it take to guard all squares of a given polyomino, the
union of square tiles from a square grid? This question is a version of the art gallery problem …