An improved algorithm for computing a shortest watchman route for lines

作者：Tan, Xuehou^*; Jiang, Bo

来源：Information Processing Letters, 2018, 131: 51-54.

DOI：10.1016/j.ipl.2017.11.011

• Computational geometry
• Watchman route problem
• Dynamic programming
• Shortest paths

We give a new algorithm to compute a shortest watchman route for a set L of n non-parallel lines in the plane. A watchman route for L is a closed curve contained in the union of the lines of L such that every line of L is visited by the route. We show that the lines visited by the shortest watchman route can be specified in order, and then present an O(n(6)) time algorithm using dynamic programming technique. Our result significantly improves upon the previous O(n(8)) time bound.

• 出版日期2018-3
• 单位大连海事大学