Guarding polygons with holes for robot motion planning applications

Abstract

The art gallery problem is aiming at finding the minimum number of guards to cover a gallery. In this paper, we consider the problem of covering a gallery with holes. The guards are required to cover a gallery that is represented as a simple polygon with n vertices and h holes. We present a robust and fast algorithm to compute a small number of vertex guards in such polygons, which runs in O(nlogn) time and uses O(n) storage. The proposed algorithm is not only offering a better performance in terms of computational cost but also ease in implementation. Simulation results demonstrate the efficiency, robustness, and potential of the proposed algorithm in motion planning systems