¹Ö±éÂêÌÜ¡§Searching a Polygonal Region from the Boundary
¹Ö±é¼Ô¡§ Ichiro Suzuki
½êÂ°¡§ Department of Electrical Engineering and Computer Science University of WisconsinMilwaukee
¹Ö±é³µÍ×¡§
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 1searcher is one whose vision is limited to the
ray of a single ashlight, while an1searcher 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 1searcher 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 sevenstate automaton for controlling the movement
of a boundary 1searcher who successfully searches any region that can
be searched by a boundary searcher. The automaton has no builtin
information about the region, and all necessary information is
acquired online 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 twodimensional
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 1searcher and an 1searcher 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
WisconsinMilwaukee. He has held visiting positions at Osaka
University and Kyushu University. His research interests include
algorithms, distributed systems, and computational geometry.
