کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414721 681013 2012 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Watchman tours for polygons with holes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Watchman tours for polygons with holes
چکیده انگلیسی

A watchman tour in a polygonal domain (for short, polygon) is a closed curve in the polygon such that every point in the polygon is visible from at least one point of the tour. We show that the length of a minimum watchman tour in a polygon P with k   holes is O(per(P)+k⋅diam(P)), where per(P)per(P) and diam(P)diam(P) denote the perimeter and the diameter of P  , respectively. Apart from the multiplicative constant, this bound is tight in the worst case. We then generalize our result to watchman tours in polyhedra with holes in 3-space. We obtain an upper bound of O(per(P)+k⋅per(P)⋅diam(P)+k2/3⋅diam(P)), which is again tight in the worst case. Our methods are constructive and lead to efficient algorithms for computing such tours.We also revisit the NP-hardness proof of the Watchman Tour Problem for polygons with holes.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 45, Issue 7, August 2012, Pages 326–333
نویسندگان
, ,