Minimization of the maximum distance between the two guards patrolling a polygonal region
Minimization of the maximum distance between the two guards patrolling a polygonal region
复制标题
DOI：
10.1016/j.tcs.2013.03.019
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
X. Tan;Bo Jiang
中科院分区：
文献类型：
--
作者：
X. Tan;Bo Jiang
两个警卫问题问两个警卫是否可以步行检测一个不可预测的，移动的目标在多边形区域P，无论目标移动有多快，如果是这样，构建一个步行时间表的警卫。为了安全起见，需要两个防护装置始终相互可见，因此它们在多边形边界上移动。特别地，直线行走要求两个卫兵在P的边界上从始至终单调地移动，一个顺时针，另一个逆时针.本文的目标是找到一个最优直线行走，使得两个卫兵之间的最大距离最小化。我们提出了一个O（n ~ 2）时间的算法来优化这个度量，其中n是顶点的个数。我们的结果是通过调查一些新的性质的themin-maxwalks和转换的问题，找到一个最佳的步行在最小-最大度量到找到一个最短的路径之间的两个节点的图。这回答了Icing和Klein提出的一个开放性问题。
Thetwo-guardproblem asks whether two guards can walk to detect an unpredictable, moving target in a polygonal regionP, no matter how fast the target moves, and if so, construct a walk schedule of the guards. For safety, two guards are required to always be mutually visible, and thus they move on the polygon boundary. In particular, astraight walkrequires both guards to monotonically move on the boundary ofPfrom beginning to end, one clockwise and the other counterclockwise.The objective of this paper is to find an optimum straight walk such that themaximumdistance between the two guards is minimized. We present anO(n2) time algorithm for optimizing this metric, wherenis the number of vertices of the polygonP. Our result is obtained by investigating a number of new properties of themin–maxwalks and converting the problem of finding an optimum walk in the min–max metric into that of finding a shortest path between two nodes in a graph. This answers an open question posed by Icking and Klein.