Searching for a Mobile Intruder in a Corridor - The Open Edge Variant of the Polygon Search Problem
Abstract
The polygon search problem is the problem of searching for mobile intruders in a simple polygon by a single mobile searcher having various degrees of visibility. This paper considers the open edge variant of the problem in which the given polygon P must be searched without allowing undetected intruders to reach a given edge u, under an additional assumption that any number of intruders can leave and enter P through another edge v at any time. One may view P as representing a corridor with two open exits u and v, and the task of the searcher is to force all the intruders out of P through v (but not u). We present a simple necessary condition for a polygon to be searchable in this manner by the searcher having a light bulb, and then show that the same condition is sufficient for the polygon to be searchable by the searcher having two flashlights. The time complexity of generating a search schedule is also discussed.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1994
- Accession Number
- ADA283918
Entities
People
- David Crass
- Ichiro Suzuki
- Masafumi Yamashita
Organizations
- University of Wisconsin–Milwaukee