Approximation algorithms for the watchman route and zookeeper's problems
2003; Elsevier BV; Volume: 136; Issue: 2-3 Linguagem: Inglês
10.1016/s0166-218x(03)00451-7
ISSN1872-6771
Autores Tópico(s)Robotic Path Planning Algorithms
ResumoGiven 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(n4) 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.
Referência(s)