The inapproximability of illuminating polygons by α-floodlights
المؤلف | Abdelkader A. |
المؤلف | Saeed A. |
المؤلف | Harras K. |
المؤلف | Mohamed A. |
تاريخ الإتاحة | 2022-04-21T08:58:32Z |
تاريخ النشر | 2015 |
اسم المنشور | Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015 |
المصدر | Scopus |
الملخص | We consider variants of the art gallery problem where guard visibility is limited to a certain angular aperture-. We show that the problem is NP-hard even when guards can be located in the interior of the polygon. We then proceed to prove that both this problem and its vertex variant, where guard placement is restricted to the vertices of the polygon, are APX-hard. We observe that earlier constructions for such results in art gallery problems with 360- guards, usually required them to cover few specific elements. We exploit this by carefully updating the construction to replace 360- guards with--floodlights. Similar transformations may be applicable to other constructions in traditional art gallery theorems, which is of independent interest. 2015 Queen's University Ontario Canada. All rights reserved. |
راعي المشروع | Qatar Foundation;�Qatar National Research Fund |
اللغة | en |
الناشر | Queen's University, Ontario, Canada |
الموضوع | Computation theory Electric lighting Floodlighting Floods Angular apertures Art gallery Art gallery problem Inapproximability NP-hard Computational geometry |
النوع | Conference Paper |
الصفحات | 287-295 |
رقم المجلد | 2015-August |
الملفات في هذه التسجيلة
الملفات | الحجم | الصيغة | العرض |
---|---|---|---|
لا توجد ملفات لها صلة بهذه التسجيلة. |
هذه التسجيلة تظهر في المجموعات التالية
-
علوم وهندسة الحاسب [2287 items ]