کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6868421 1439974 2018 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Tight bounds for conflict-free chromatic guarding of orthogonal art galleries
ترجمه فارسی عنوان
محدوده تنگ برای محافظت از رنگ آمیزی مصنوعی از گالری های هنری متعامد
کلمات کلیدی
چند ضلعی ارتجاعی، مشکل گالری هنر رنگ آمیزی بیش از حد،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The chromatic art gallery problem asks for the minimum number of “colors” t so that a collection of point guards, each assigned one of the t colors, can see the entire polygon subject to some conditions on the colors visible to each point. In this paper, we explore this problem for orthogonal polygons using orthogonal visibility-two points p and q are mutually visible if the smallest axis-aligned rectangle containing them lies within the polygon. Our main result establishes that for a conflict-free guarding of an orthogonal n-gon, in which at least one of the colors seen by every point is unique, the number of colors is in the worst case Θ(log⁡log⁡n). By contrast, the best known upper bound for orthogonal polygons under standard (non-orthogonal) visibility is O(log⁡n) colors. We also show that the number of colors needed for strong guarding of simple orthogonal polygons, where all the colors visible to a point are unique, is, again in the worst case, Θ(log⁡n). Finally, our techniques also help us establish the first non-trivial lower bound of Ω(log⁡log⁡n/log⁡log⁡log⁡n) for conflict-free guarding under standard visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 73, August 2018, Pages 24-34
نویسندگان
, , , , ,