Searching for mobile intruders in a polygonal region by a group of mobile searchers
The problem of searching for mobile intruders in a polygonal region by mobile searchers is considered. A searcher can move continuously inside a polygon holding a flashlight that emits a single ray of light whose direction can be changed continuously. The vision of a searcher at any time instant is limited to the points on the ray. The intruders can move continuously with unbounded speed. We denote by ps(P) the polygon search number of a simple polygon P, which is the number of searchers necessary and sufficient to search P. Let n, r, b, and g be the number of edges, the number of reflex vertices, the bushiness, and the size of a minimum guard set of P, respectively. In this paper we present matching upper and (worst case) lower bounds of 1 + right perpendicular log(3)(2b + 1) left perpendicular on ps(P). Also upper bounds on ps(P) in terms of n, r, and g are presented; ps(P) less than or equal to 1 + right perpendicular log(3)(n - 3) left perpendicular, ps(P) less than or equal to 1 + right perpendicular log(3) left perpendicular, and ps(P) less than or equal to 2 + inverted right perpendicular log(2) g inverted left perpendicular. These upper bounds are tight or almost tight in the worst case, since we show that for any natural number s greater than or equal to 2, there is a polygon P such that ps(P) = log(3)(n + 1) = log(3)(2r + 3) = 1 + log(3)(2g - 1) = s.
polygon search number polygon search problem searchlight problem graph search problem art gallery problem multirobot system