### A linear time algorithm for optimal routing around a rectangleA linear time algorithm for optimal routing around a rectangle

Access Restriction
Subscribed

 Author Gonzalez, Teofilo F. ♦ Lee, Sing-Ling Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1988 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract The problem of connecting a set of terminals that lie on the sides of a rectangle to minimize the total area is discussed. An $\textit{O}(\textit{n})$ algorithm is presented to solve this problem when the set of $\textit{n}$ terminals is initially sorted. The strategy in this paper is to reduce the problem to several problems such that no matter what instance is started with, at least one of these problems can be solved optimally by a greedy method. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1988-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 35 Issue Number 4 Page Count 22 Starting Page 810 Ending Page 831

#### Open content in new tab

Source: ACM Digital Library