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 + \lfloor log 3 (2b+1) floor on ps(P) . Also upper bounds on ps(P) in terms of n,r , and g are presented;ps(P) ≤ 1 + \lfloor log 3 (n‐3) floor, ps(P) ≤ 1 + \lfloor log 3 r floor , and ps(P) ≤ 2 + \lceil log 2 g ceil . These upper bounds are tight or almost tight in the worst case, since we show that for any natural number s \geq 2 , there is a polygon P such that ps(P) = log 3 (n+1) = log 3 (2r+3) = 1 + log 3 (2g‐1) = s .