On Some City Guarding Problems

摘要：

We consider guarding a city of k vertical buildings, each having a rectangular base, by placing guards only at vertices. The aim is to use the smallest number of guards. The problem is a 2.5D variant of the traditional art gallery problem, and finds applications in urban security. We give upper and lower bounds on the number of guards needed for a few versions of the problem.

作者: Lichen Bao Sergey Bereg Ovidiu Daescu Simeon Ntafos Junqiang Zhou

作者单位: Department of Computer Science Erik Jonsson School of Engineering & Computer Science The University Department of Computer Science Erik Jonsson School of Engineering & Computer Science The University

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 600-610

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）