Corrigendum to "An Incremental Algorithm for Constructing Shortest Watchman Routes"
Corrigendum to "An Incremental Algorithm for Constructing Shortest Watchman Routes"
复制标题
“构建最短看守路线的增量算法”的勘误表
DOI：
10.1142/s0218195999000212
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Y. Inagaki
中科院分区：
文献类型：
--
作者：
X. Tan;T. Hirata;Y. Inagaki
考虑寻找简单多边形 P 中通过其边界上的点 s 的最短看守路线的问题。如果一条路线是一条看守路线，则该路线上的至少一个点可以看到 P 内的每个点。我们提出了一种增量算法，可以在 O(n3) 时间内为具有 n 条边的简单多边形构造最短的看守路线。这改进了之前的 O(n4) 界限。
The problem of finding the shortest watchman route in a simple polygon P through a point s on its boundary is considered. A route is a watchman route if every point inside P can be seen from at least one point along the route. We present an incremental algorithm that constructs the shortest watchman route in O(n3) time for a simple polygon with n edges. This improves the previous O(n4) bound.