肥後研究室
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:
- 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.
- 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.