Abstract | ||
---|---|---|
A watchman, in the terminology of art galleries, is a mobile guard. We consider severalwatchman and guard problems for different classes of polygons. We introduce the notion ofvision spans along a path (route) which provide a natural connection between the Art Galleryproblem, the m-watchmen problem and the watchman route problem. We prove that findingthe minimum number of vision points, i.e., static guards, along a shortest watchman routeis NP-hard. We provide a linear time algorithm... |
Year | DOI | Venue |
---|---|---|
1993 | 10.1007/BFb0028276 | Int. J. Comput. Geometry Appl. |
DocType | Volume | Issue |
Journal | 3 | 1 |
Citations | PageRank | References |
8 | 0.93 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Svante Carlsson | 1 | 764 | 90.17 |
Bengt J. Nilsson | 2 | 210 | 24.43 |
Simeon C. Ntafos | 3 | 599 | 98.18 |