Searching for a mobile intruder in a polygonal region

Ichiro Suzuki, Masafumi Yamashita

Research output: Contribution to journalArticlepeer-review

222 Citations (Scopus)


The problem of searching for a mobile intruder in a simple polygon by a single mobile searcher is considered. This paper investigates the capabilities of searchers having different degrees of visibility by introducing the searcher having k flashlights whose visibility is limited to k rays emanating from his position, and the searcher having a point light source who can see in all directions simultaneously. This paper presents necessary and sufficient conditions for a polygon to be searchable by various searchers. The paper also introduces a class of polygons for which the searcher having two flashlights is as capable as the searcher having a point light source, and it gives a simple necessary and sufficient condition for such polygons to be searchable by the searcher having two flashlights. The complexity of generating a search schedule under some of these conditions is also discussed. Many of the results are proved using chord systems that represent the visibility relations among the vertices and edges of the given polygon.

Original languageEnglish
Pages (from-to)863-888
Number of pages26
JournalSIAM Journal on Computing
Issue number5
Publication statusPublished - 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Searching for a mobile intruder in a polygonal region'. Together they form a unique fingerprint.

Cite this