Advertisement
Published in:
2012 | OriginalPaper | Chapter
Minimization of the Maximum Distance between the Two Guards Patrolling a Polygonal Region
Authors : Xuehou Tan, Bo Jiang
Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The
two-guard
problem asks whether two guards can walk to detect an unpredictable, moving target in a polygonal region
P
, no matter how fast the target moves, and if so, construct a walk schedule of the guards. For safety, two guards are required to always be mutually visible, and thus, they move on the polygon boundary. Specially, a
straight walk
requires both guards to monotonically move on the boundary of
P
from beginning to end, one clockwise and the other counterclockwise.
The objective of this paper is to find an optimum straight walk such that the
maximum
distance between the two guards is minimized. We present an
O
(
n
2
log
n
) time algorithm for optimizing this metric, where
n
is the number of vertices of the polygon
P
. Our result is obtained by investigating a number of new properties of the
min-max
walks and converting the problem of finding an optimum walk in the min-max metric into that of finding a shortest path between two nodes in a graph. This answers an open question posed by Icking and Klein.