Department of Electrical Engineering and Computer Science, University of
Wisconsin-Milwaukee
講演題目
Searching a Polygonal Region from the Boundary
概要
Polygon search is the problem of finding 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
flashlight, while an ∞-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
∞-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 unified 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
∞-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.) <P> 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.