Online polygon search by a seven-state boundary 1-searcher

Tsunehiko Kameda, Masafumi Yamashita, Ichiro Suzuki

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)


Polygon search is the problem of finding mobile intruders who move unpredictably in a polygonal region. In this paper, we consider a special case of this problem, called boundary search, where the searcher is allowed to move only along the boundary of the polygon. We concentrate on a single searcher with one flashlight (called a 1-searcher), but it is known that a single boundary 1-searcher has the same searching power as a single boundary searcher with 360° vision. Our main result is that the movement of the searcher can be controlled by a finite-state machine having only seven states. This automaton has no built-in information about the input polygon and, for any given polygon can be searched by a boundary searcher at all, then this automaton will successfully search P no matter where on the boundary of P it is initially placed. All information about P is acquired by the automaton online, as it searches P. We also show that if P can be searched by a boundary searcher, then our automaton searches it by circling its boundary less than three times.

Original languageEnglish
Pages (from-to)446-460
Number of pages15
JournalIEEE Transactions on Robotics
Issue number3
Publication statusPublished - Jun 2006

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Online polygon search by a seven-state boundary 1-searcher'. Together they form a unique fingerprint.

Cite this