Book ; Online: Guarding Polyominoes under $k$-Hop Visibility
2023
Abstract: We study the Art Gallery Problem under $k$-hop visibility in polyominoes. In this visibility model ... the respective vertices in the dual graph of the polyomino has length at most $k$. In this paper, we show ... not contain a $3\times 3$ block of cells) for all $k\in \mathbb{N}$. ...
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 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$ 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$ block of cells) for all $k\in \mathbb{N}$. Comment: 17 pages, 11 figures. Full version of an extended abstract that has been accepted to LATIN 2024. Some parts have been improved based on reviewer comments |
---|---|
Keywords | Computer Science - Computational Geometry ; Computer Science - Data Structures and Algorithms ; F.2.2 |
Subject code | 511 |
Publishing date | 2023-08-01 |
Publishing country | us |
Document type | Book ; Online |
Database | BASE - Bielefeld Academic Search Engine (life sciences selection) |
Full text online
More links
Kategorien
Inter-library loan at ZB MED
Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.