Guarding Polyominoes Under k-Hop Visibility

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×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
מספר עמודים15
מסת"ב (מודפס)9783031555978
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2024
אירוע16th Latin American Symposium on Theoretical Informatics, LATIN 2042 - Puerto Varas, צ'ילה
משך הזמן: 18 מרץ 202422 מרץ 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

הערה ביבליוגרפית

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Guarding Polyominoes Under k-Hop Visibility'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי