ֱܡSearching a Polygonal Region from the Boundary

ֱԡ Ichiro Suzuki

° Department of Electrical Engineering and Computer Science University of Wisconsin-Milwaukee


ֱ鳵ס

Polygon search is the problem of nding mobile intruders who move
unpredictably in a polygonal region, using one or more mobile
searchers. Various levels of vision are assumed to model the ability
of the searchers | a 1-searcher is one whose vision is limited to the
ray of a single ashlight, while an1-searcher has a light bulb that
gives 360 vision. In this talk we consider a special case of the
problem where a given region must be searched by boundary searchers
who are allowed to move only along the region boundary. We present two
results:

1. A single boundary 1-searcher is just as capable as a single
boundary 1- searcher, that is, any region that can be searched by the
latter can also be searched by the former.


2. There exists a seven-state automaton for controlling the movement
of a boundary 1-searcher who successfully searches any region that can
be searched by a boundary searcher. The automaton has no built-in
information about the region, and all necessary information is
acquired on-line as it searches the region. The automaton may not
terminate, however, if the region is not searchable by a boundary
searcher.

 We obtain these results in a uni ed manner by representing
the movement of a searcher as a directed path in a two-dimensional
boundary visibility diagram. The use of the diagram has allowed us to
give simple, intuitive proofs; for instance, the proof of the
equivalence of a 1-searcher and an 1-searcher would have been much
more complex if we had attempted a "direct simulation" of the latter
by the former in a given region. (Joint work with T. Kameda, Y. Tazoe
and M. Yamashita.)



Ichiro Suzuki received his D.E. degree in Information and Computer
Sciences from Osaka University, Japan, in 1983. He is currently a
Professor of Computer Science at the University of
Wisconsin-Milwaukee. He has held visiting positions at Osaka
University and Kyushu University. His research interests include
algorithms, distributed systems, and computational geometry.