Approximation algorithms for the watchman route and zookeeper's problems

✍ Scribed by Xuehou Tan

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 261 KB
• Volume: 136
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00451-7

✦ Synopsis

Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most √ 2 times that of the shortest watchman route. The best known algorithm for computing the shortest watchman route through s takes O(n 4 ) time. In addition, it is too complicated to be suitable in practice. Moreover, our approximation scheme can be applied to the zookeeper's problem, which is a variant of the watchman route problem. ?