תקציר
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×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.
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | LATIN 2024 |
כותר משנה של פרסום המארח | Theoretical Informatics - 16th Latin American Symposium, 2024, Proceedings |
עורכים | José A. Soto, Andreas Wiese |
מוציא לאור | Springer Science and Business Media Deutschland GmbH |
עמודים | 288-302 |
מספר עמודים | 15 |
מסת"ב (מודפס) | 9783031555978 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 2024 |
אירוע | 16th Latin American Symposium on Theoretical Informatics, LATIN 2042 - Puerto Varas, צ'ילה משך הזמן: 18 מרץ 2024 → 22 מרץ 2024 |
סדרות פרסומים
שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
כרך | 14578 LNCS |
ISSN (מודפס) | 0302-9743 |
ISSN (אלקטרוני) | 1611-3349 |
כנס
כנס | 16th Latin American Symposium on Theoretical Informatics, LATIN 2042 |
---|---|
מדינה/אזור | צ'ילה |
עיר | Puerto Varas |
תקופה | 18/03/24 → 22/03/24 |
הערה ביבליוגרפית
Publisher Copyright:© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.