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 -