FACULTY OF TECHNOLOGY AND SOCIETY | Seminar
Guarding Polyominoes Under k-Hop Visibility

Title

Guarding Polyominoes Under k-Hop Visibility.

Welcome to a seminar with Christiane Schmidt, Senior Associate Professor at the Communications and Transport Systems division at Linköping University.

In this talk, we consider 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 path between the respective vertices in the dual graph of the polyomino has length at most k. We show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we show that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2 × 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3 × 3 block of cells) for all k ∈ N.

The talk is based on joint work with Omrit Filtser, Erik Krohn, Bengt J. Nilsson, and Christian Rieck