Pursuit Evasion in Simple Polygons

Date
2014-03
Authors
Majeed, Babar
Journal Title
Journal ISSN
Volume Title
Publisher
Faculty of Graduate Studies and Research, University of Regina
Abstract

Pursuit evasion in simple polygons is fundamentally searching for an evader in a simple polygon. Popular problems in polygon searching include the room search problem and the two guard problem. Many practical applications, such as search for an evader in a dark house, rescue of a victim in a dangerous building and surveillance with autonomous mobile robots, can be modeled by polygon search problems. In this thesis, we investigate two problems related to polygon searching. The rst problem which we study is searching for a mobile evader in a simple polygonal room with two doors by a boundary 2-searcher. The boundary 2-searcher is a searcher which is equipped with two ashlights with a limited visibility, i.e., only in the direction of ray shots emanating from his position, which can only move on the boundary of polygonal region. We give necessary and su cient conditions for a simple polygonal room to be searchable by a boundary 2-searcher. We propose an algorithm for generating the search schedule, if it exists. We also show that searching a room using a boundary 2-searcher requires at most O(n2) edge traversals. The second problem which we consider is searching for a mobile evader in a simple polygon using a pair of searchers. Each searcher is equipped with a single ashlight and he can see only along the direction of ray emanating from its position. The searchers are allowed to move on the boundary of the simple polygon. The pair of searchers has to detect the evader at least once using any of two ashlights. We present three necessary conditions for a simple polygon to be searchable by a pair of searchers. We also study the capabilities of a boundary and non-boundary pair of searchers.

Description
A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Science, University of Regina. x, 65 p.
Keywords
Citation
Collections