| Abstract Chapter 51 The Aquarium Keeper’s Problem* (2009) | |||||||||||||||
Abstract | |||||||||||||||
| We solve the problem of computing the shortest closed path inside a given polygon which visits every edge at least once (Aquarium Z{eeper’s Tour). For convex polygons, we present a linear-time algorithm which uses the reflection principle and shortest-path maps. We then generalize that method by using relative convex hulls to provide a linear algorithm for polygons which are not convex. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||