کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428298 | 686632 | 2007 | 6 صفحه PDF | دانلود رایگان |

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.
Journal: Information Processing Letters - Volume 102, Issues 2–3, 30 April 2007, Pages 66-71