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 path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is <Emphasis FontCategory="SansSerif">NP</Emphasis>-complete even in thin polyominoes (i.e., polyominoes that do not a contain a <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2024_1292_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$2\times 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mo>×</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2024_1292_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">$3\times 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>3</mn> <mo>×</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> block of cells) for all <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="453_2024_1292_Article_IEq3.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">$k\in {\mathbb {N}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>∈</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation>.

Guarding Polyominoes Under k-Hop Visibility

期刊论文
出版模式：

开放获取
发表日期：

2025年1月11日

查看全文

Omrit Filtser,
Erik Krohn,
Bengt J. Nilsson,
Christian Rieck,
Christiane Schmidt

摘要

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 path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a $2\times 2$ $2 \times 2$ block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a $3\times 3$ $3 \times 3$ block of cells) for all $k\in {\mathbb {N}}$ $k \in N$ .