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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2024
الحدث16th Latin American Symposium on Theoretical Informatics, LATIN 2042 - Puerto Varas, تشيلي
المدة: ١٨ مارس ٢٠٢٤٢٢ مارس ٢٠٢٤

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت14578 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349


!!Conference16th 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'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا