首页 | 本学科首页   官方微博 | 高级检索  
     


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, USA
  • b 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 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

    Copyright©北京勤云科技发展有限公司  京ICP备09084417号