کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420438 | 683937 | 2010 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for art gallery problems in polygons
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Approximation algorithms for art gallery problems in polygons Approximation algorithms for art gallery problems in polygons](/preview/png/420438.png)
چکیده انگلیسی
In this paper, we present approximation algorithms for minimum vertex and edge guard problems for polygons with or without holes with a total of nn vertices. For simple polygons, approximation algorithms for both problems run in O(n4)O(n4) time and yield solutions that can be at most O(logn)O(logn) times the optimal solution. For polygons with holes, approximation algorithms for both problems give the same approximation ratio of O(logn)O(logn), but the running time of the algorithms increases by a factor of nn to O(n5)O(n5).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 6, 28 March 2010, Pages 718–722
Journal: Discrete Applied Mathematics - Volume 158, Issue 6, 28 March 2010, Pages 718–722
نویسندگان
Subir Kumar Ghosh,