Advertisement
Published in:
2010 | OriginalPaper | Chapter
Optimum Sweeps of Simple Polygons with Two Guards
Authors : Xuehou Tan, Bo Jiang
Published in: Frontiers in Algorithmics
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
A polygon
P
admits a
sweep
if two mobile guards can detect an unpredictable, moving target inside
P
, no matter how fast the target moves. For safety, two guards are required to always be mutually visible, and thus, they should move on the polygon boundary. Our objective in this paper is to find an optimum sweep such that the sum of the distances travelled by the two guards in the sweep is minimized. We present an
O
(
n
2
) time and
O
(
n
) space algorithm, where
n
is the number of vertices of the given polygon. This new result is obtained by converting the problem of sweeping simple polygons with two guards into that of finding a shortest path between two nodes in a graph of size
O
(
n
).