Optimum sweeps of simple polygons with two guards

• This is the first work on finding an optimum sweep of the polygon with two guards.
• Any optimum sweep of the min-sum distance can be divided into O(n)O(n) canonical sweeps.
• A data structure has been developed to record the canonical sweeps.
• We have obtained an O(n2)O(n2) time and O(n)O(n) space solution to this problem.

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. Two guards move on the polygon boundary and are required to always be mutually visible. The objective of this study 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(n2)O(n2) time and O(n)O(n) space algorithm for optimizing this metric, where n   is the number of vertices of the given polygon. Our result is obtained by reducing this problem to finding a shortest path between two nodes in a graph of size O(n)O(n).