Finding shortest safari routes in simple polygons

✍ Scribed by Xuehou Tan; Tomio Hirata

• Book ID: 104136979
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 144 KB
• Volume: 87
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(03)00284-9

✦ Synopsis

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. Geom. 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.