کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428298 686632 2007 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sweeping simple polygons with the minimum number of chain guards
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Sweeping simple polygons with the minimum number of chain guards
چکیده انگلیسی

We study the problem of detecting a moving target using a group of k+1 (k is a positive integer) mobile guards inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that consecutive guards along the chain are mutually visible. In this paper, we introduce the notion of the link-k diagram of a polygon, which records the pairs of points on the polygon boundary such that the link distance between any of these pairs is at most k and a transition relation among minimum-link (⩽k) paths as well. An O(n2) time algorithm is then presented to compute the minimum number r* of guards required to detect the target, no matter how fast the target moves. Moreover, a sweep schedule can be reported in O(r*n2) time. Our results improve upon the known time bounds by a linear factor.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 102, Issues 2–3, 30 April 2007, Pages 66-71