Portal de Periódicos da CAPES

OPTIMUM GUARD COVERS AND m-WATCHMEN ROUTES FOR RESTRICTED POLYGONS

1993; World Scientific; Volume: 03; Issue: 01 Linguagem: Inglês

10.1142/s0218195993000063

1793-6357

Svante Carlsson, Bengt J. Nilsson, Simeon Ntafos,

Remote Sensing and LiDAR Applications

A watchman, in the terminology of art galleries, is a mobile guard. We consider several watchman and guard problems for different classes of polygons. We introduce the notion of vision spans along a path or route which provide a natural connection between the art gallery problem, the m-watchmen routes problem and the watchman route problem. We prove that finding the minimum number of vision points, i.e., static guards, along a shortest watchman route is NP-hard. We provide a linear time algorithm to compute the best set of static guards in a histogram polygon. The m-watchmen routes problem, minimize total length of routes for m watchmen, is NP-hard for simple polygons. We give a Θ(n 3 +n 2 m 2 )-time algorithm to compute the best set of m watchmen in a histogram.