The Aquarium Keeper's problem

Jurek Czyzowicz, Peter Egyed, Hazel Everett, David Rappaport, Thomas Shermer, Diane Souvaine, Godfried Toussaint, Jorge Urrutia

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We solve the problem of computing the shortest closed path inside a given polygon which visits every edge at least once (Aquarium Keeper'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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
PublisherAssociation for Computing Machinery
Pages459-464
Number of pages6
ISBN (Print)0897913760
StatePublished - Mar 1 1991
Event2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States
Duration: Jan 28 1991Jan 30 1991

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
CountryUnited States
CitySan Francisco
Period1/28/911/30/91

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The Aquarium Keeper's problem'. Together they form a unique fingerprint.

Cite this