An improved algorithm for computing a shortest watchman route for lines

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(n6) time algorithm using dynamic programming technique. Our result significantly improves upon the previous O(n8) time bound.