The is the problem of searching for a mobile intruder in a simple polygon by a mobile searcher. The objective is to decide whether there exists a for the searcher to detect the intruder, no matter how fast he moves, and if so, generate a search schedule. A searcher is called the if he holds flashlights and can see only along the rays of the flashlights emanating from his position, and the ∞- if he has a 360° field of vision. We first present necessary and sufficient conditions for the polygons to be searchable by 1-searchers, and give an ( log ) time and () space algorithm for testing the 1-searchability of simple polygons, and an ( log + ) time algorithm for generating a search schedule if it exists, where (≤ ) is the number of search instructions output. The key ideas include an ingenious identification of critical visibility events and a decomposition of the search schedule based on these events. We then extends the results obtained for 1-searchers to those for 2-searchers, with the time bounds changed to (). We also show that any polygon that is searchable by an ∞-searcher is searchable by a 2-searcher. Our results solve a long-standing open problem in computational geometry and robotics, and confirm a conjecture due to Suzuki and Yamashita
