论文标题
旋转单调可见性下的简单多边形的最短守望者游览
Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility
论文作者
论文摘要
我们提出了一种$ O（NRG）$时间算法，用于计算和保持最小长度最短的守望者巡回演出，该巡回演出在单个方向$θ$的单调可见度下看到一个简单的多边形，而$θ$在$ [0,180^{\ circ}）$中变化，可获得所有$ n $ n $ n $ north $ n $ norker $ n $ n $ n $ n $ n $ n $ n $ n $ norker norks norme a $ north $ n $反射顶点和$ g \ leq r $是算法中随时使用的多边形的最大门数。
We present an $O(nrG)$ time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction $θ$, while $θ$ varies in $[0,180^{\circ})$, obtaining the directions for the tour to be the shortest one over all tours, where $n$ is the number of vertices, $r$ is the number of reflex vertices, and $G\leq r$ is the maximum number of gates of the polygon used at any time in the algorithm.
