Finding shortest safari routes in simple polygons
Let P be a simple polygon, and let P be a set of disjoint convex polygons inside P, each sharing one edge with P. The safari route problem asks for a shortest route inside P that visits each polygon in P. In this paper, we first present a dynamic programming algorithm with running time O(n(3)) for computing the shortest safari route in the case that a starting point on the route is given, where n is the total number of vertices of P and polygons in P. (Ntafos in [Comput. Geont. 1 (1992) 149-170] claimed a more efficient solution, but as shown in Appendix A of this paper, the time analysis of Ntafos' algorithm is erroneous and no time bound is guaranteed for his algorithm.) The restriction of giving a starting point is then removed by a brute-force algorithm, which requires O(n(4)) time. The solution of the safari route problem finds applications in watchman routes under limited visibility. (C) 2003 Elsevier B.V. All rights reserved.
safari routes computational geometry zookeeper's routes adjustments