The Aquarium Keeper's problem

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

The Aquarium Keeper's problem

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Publisher	Association for Computing Machinery
Pages	459-464
Number of pages	6
ISBN (Print)	0897913760
State	Published - Mar 1 1991
Event	2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States Duration: Jan 28 1991 → Jan 30 1991

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other	2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Country	United States
City	San Francisco
Period	1/28/91 → 1/30/91

ASJC Scopus subject areas

Software
Mathematics(all)

Access to Document

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

Cite this

The Aquarium Keeper's problem. / Czyzowicz, Jurek; Egyed, Peter; Everett, Hazel; Rappaport, David; Shermer, Thomas; Souvaine, Diane; Toussaint, Godfried; Urrutia, Jorge.

Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery, 1991. p. 459-464 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Czyzowicz, J, Egyed, P, Everett, H, Rappaport, D, Shermer, T, Souvaine, D, Toussaint, G & Urrutia, J 1991, The Aquarium Keeper's problem. in Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 459-464, 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991, San Francisco, United States, 1/28/91.

Czyzowicz, Jurek ; Egyed, Peter ; Everett, Hazel ; Rappaport, David ; Shermer, Thomas ; Souvaine, Diane ; Toussaint, Godfried ; Urrutia, Jorge. / The Aquarium Keeper's problem. Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991. Association for Computing Machinery, 1991. pp. 459-464 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

@inproceedings{000641d3624e41cf975ecdcceee9baf8,

title = "The Aquarium Keeper's problem",

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.",

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

year = "1991",

month = mar,

day = "1",

language = "English (US)",

isbn = "0897913760",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "459--464",

booktitle = "Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991",

note = "2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 ; Conference date: 28-01-1991 Through 30-01-1991",

}

TY - GEN

T1 - The Aquarium Keeper's problem

AU - Czyzowicz, Jurek

AU - Egyed, Peter

AU - Everett, Hazel

AU - Rappaport, David

AU - Shermer, Thomas

AU - Souvaine, Diane

AU - Toussaint, Godfried

AU - Urrutia, Jorge

PY - 1991/3/1

Y1 - 1991/3/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=85032002331&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032002331&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85032002331

SN - 0897913760

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 459

EP - 464

BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

PB - Association for Computing Machinery

T2 - 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991

Y2 - 28 January 1991 through 30 January 1991

ER -