The Aquarium Keeper's Problem
Jurek Czyzowicz, Peter Egyed, Hazel Everett, David D. Rappaport, Thomas Caton Shermer, Diane L. Souvaine, Godfried Toussaint, Jorge Urrutia · Symposium on Discrete Algorithms · 1991
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.