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

N1 - Funding Information:
Although variously attributed to Fagnano [11] and Steiner [5] ,[9] ,[15] ,[14], many sources insist that, over one hundred years ago, Schwarz not only solved the problem of computing the minimum perimeter triangle with one vertex on each edge of a given triangle but that he also posed the problem [4] ,[8] ,[12] ,[13]. In any case, there is consensus that Schwarz used the reelection principle to show that the foot points of the altitudes of an acute triangle are the vertices of the minimum inscribed polygon. For obtuse triangles, the minimum perimeter inscribed triangle is realized by twice the shortest altitude, i.e. it is degenerate with two vertices coinciding with the obtuse vertex of the input triangle. The earliest problem solved with the reflection principle was even simpler than the triangle: given a line and two points on one side of it, find the shortest path between the two points via the line. This problem was solved by *Pm-t of the work was carried out when the authom were participants of the Workshop on Illuminating Sets at the Bellairs Research Institute of McGill University. tDepartment d’Inforrnzkique, Universit6 du Quebech Hull, Hull, Quebec, CANADA. $s&ool of Computer Science, McGill University, Montreal, Quebec, CANADA H3S 2A7. $D~pw@ent of computing and Information Science, Queen’s University, Kingston, Ontario, CANADA K7L 3N6. 11S&X-J of Computing Science, Simon Fraser University, Burn-aby, British Col-bi., CANADA V5A 1S6. IIDepartment of Computer Science, Rutgers University, New Brunswick, New Jersey, USA 08903. Supported in part by NSF Grant CCR-8S-03549. **Department of Computer Science, University of Ottawa, Ottawa, Ontario, CANADA KIN 6N5.

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 -