Guarding a set of line segments in the plane |
| |
Authors: | Valentin E. Brimkov Andrew Leach |
| |
Affiliation: | a Mathematics Department, SUNY Buffalo State College, Buffalo, NY 14222, USAb Mathematics Department, University at Buffalo, Buffalo, NY 1426-2900, USA |
| |
Abstract: | We consider the following problem: Given a finite set of straight line segments in the plane, find a set of points of minimum size, so that every segment contains at least one point in the set. This problem can be interpreted as looking for a minimum number of locations of policemen, guards, cameras or other sensors, that can observe a network of streets, corridors, tunnels, tubes, etc. We show that the problem is strongly NP-complete even for a set of segments with a cubic graph structure, but in P for tree structures. |
| |
Keywords: | Art-gallery problem Guarding set of segments Strongly NP-complete problem Polynomial algorithm Set cover Vertex cover |
本文献已被 ScienceDirect 等数据库收录! |
|