{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:30:01Z","timestamp":1757626201716,"version":"3.44.0"},"reference-count":44,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1988,5,1]],"date-time":"1988-05-01T00:00:00Z","timestamp":578448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[1988,5,1]],"date-time":"1988-05-01T00:00:00Z","timestamp":578448000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Integration"],"published-print":{"date-parts":[[1988,5]]},"DOI":"10.1016\/0167-9260(88)90017-x","type":"journal-article","created":{"date-parts":[[2003,3,14]],"date-time":"2003-03-14T14:37:33Z","timestamp":1047652653000},"page":"35-57","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":14,"title":["Optimal two-terminal \u03b1-\u03b2 wire routing"],"prefix":"10.1016","volume":"6","author":[{"given":"J.P.","family":"Cohoon","sequence":"first","affiliation":[]},{"given":"D.S.","family":"Richards","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"year":"1974","author":"Aho","key":"10.1016\/0167-9260(88)90017-X_BIB1"},{"issue":"9","key":"10.1016\/0167-9260(88)90017-X_BIB2","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","article-title":"Algorithms for reporting and counting geometric intersections","volume":"C-28","author":"Bentley","year":"1979","journal-title":"IEEE Trans. Comput."},{"issue":"7","key":"10.1016\/0167-9260(88)90017-X_BIB3","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1109\/TC.1980.1675628","article-title":"An optimal worst-case algorithm for reporting intersections of rectangles","volume":"C-29","author":"Bentley","year":"1980","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0167-9260(88)90017-X_BIB4","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/366105.366184","article-title":"On finding minimum routes in a network with turn penalties","volume":"4","author":"Caldwell","year":"1961","journal-title":"Comm. ACM"},{"article-title":"A line intersection algorithm for the routing problem","year":"1984","author":"Cohoon","key":"10.1016\/0167-9260(88)90017-X_BIB5"},{"key":"10.1016\/0167-9260(88)90017-X_BIB6","series-title":"Proc. Symp. Computational Geometry","first-page":"204","article-title":"Rectilinear shortest paths with rectangular barriers","author":"De Rezende","year":"1985"},{"key":"10.1016\/0167-9260(88)90017-X_BIB7","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"issue":"6","key":"10.1016\/0167-9260(88)90017-X_BIB8","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","article-title":"Fast algorithms for shortest paths in planar graphs, with applications","volume":"16","author":"Frederickson","year":"1987","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0167-9260(88)90017-X_BIB9","first-page":"338","article-title":"Fibonacci heaps and their uses in improved network optimization","author":"Fredman","year":"1984"},{"key":"10.1016\/0167-9260(88)90017-X_BIB10","first-page":"168","article-title":"Dynamization of geometric data structures","author":"Fries","year":"1985"},{"key":"10.1016\/0167-9260(88)90017-X_BIB11","series-title":"Proc. 15th Annual ACM Symp. Theory of Computing","article-title":"A linear-time algorithm for a special case of disjoint set union","author":"Gabow","year":"1983"},{"key":"10.1016\/0167-9260(88)90017-X_BIB12","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0196-6774(84)90013-0","article-title":"An optimal contour algorithm for iso-oriented rectangles","volume":"5","author":"G\u00fcting","year":"1984","journal-title":"J. Algorithms"},{"key":"10.1016\/0167-9260(88)90017-X_BIB13","first-page":"165","article-title":"Fast dynamic searching in a set of isothetic line segments","volume":"21","author":"G\u00fcting","year":"1985"},{"key":"10.1016\/0167-9260(88)90017-X_BIB14","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/net.3230070404","article-title":"A shortest path algorithm for grid graphs","volume":"7","author":"Hadlock","year":"1977","journal-title":"Networks"},{"year":"1972","author":"Harary","key":"10.1016\/0167-9260(88)90017-X_BIB15"},{"key":"10.1016\/0167-9260(88)90017-X_BIB16","series-title":"17th Design Automation COnfer. Proc.","first-page":"243","article-title":"A line-expansion algorithm for the general routing problem with a guaranteed solution","author":"Heyns","year":"1980"},{"key":"10.1016\/0167-9260(88)90017-X_BIB17","series-title":"6th Design Automation Workshop Proc.","first-page":"1","article-title":"A solution to the line-routing problem on the continuous plane","author":"Hightower","year":"1969"},{"issue":"4","key":"10.1016\/0167-9260(88)90017-X_BIB18","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/MC.1974.6323494","article-title":"The interconnection problem: a tutorial","volume":"7","author":"Hightower","year":"1974","journal-title":"Computer"},{"year":"1978","author":"Horowitz","key":"10.1016\/0167-9260(88)90017-X_BIB19"},{"key":"10.1016\/0167-9260(88)90017-X_BIB20","first-page":"139","article-title":"The \u03b1-\u03b2 Routing","author":"Hu","year":"1985"},{"issue":"3","key":"10.1016\/0167-9260(88)90017-X_BIB21","first-page":"141","article-title":"Shortest path algorithms for graphs of restricted in-degree and out-degree","volume":"EIK 18","author":"Hubler","year":"1982","journal-title":"Elektronische Informationsverarbeitung und Kybernetik"},{"key":"10.1016\/0167-9260(88)90017-X_BIB22","first-page":"393","article-title":"Dynamic segment intersection search with applications","author":"Imai","year":"1984"},{"key":"10.1016\/0167-9260(88)90017-X_BIB23","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/S0041-1647(69)80022-5","article-title":"The minimum route problem for networks with turn penalties and prohibitions","volume":"3","author":"Kirby","year":"1969","journal-title":"Transportation Research"},{"key":"10.1016\/0167-9260(88)90017-X_BIB24","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/net.3230110307","article-title":"Finding minimum rectilinear distance paths in the presence of obstacles","volume":"11","author":"Larson","year":"1981","journal-title":"Networks"},{"key":"10.1016\/0167-9260(88)90017-X_BIB25","series-title":"17th Design Automation Confer. Proc.","first-page":"603","article-title":"A data structure for gridless routing","author":"Lauther","year":"1980"},{"issue":"3","key":"10.1016\/0167-9260(88)90017-X_BIB26","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1109\/TEC.1961.5219222","article-title":"An algorithm for path connections and its applications","volume":"EC-10","author":"Lee","year":"1961","journal-title":"IRE Trans. Electronic Comput."},{"article-title":"Proximity and Reachability in the Plane","year":"1978","author":"Lee","key":"10.1016\/0167-9260(88)90017-X_BIB27"},{"key":"10.1016\/0167-9260(88)90017-X_BIB28","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","article-title":"Euclidean shortest paths in the presence of rectilinear barriers","volume":"14","author":"Lee","year":"1984","journal-title":"Networks"},{"key":"10.1016\/0167-9260(88)90017-X_BIB29","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1002\/net.3230130308","article-title":"Finding a Manhattan path and related problems","volume":"13","author":"Lipski","year":"1983","journal-title":"Networks"},{"key":"10.1016\/0167-9260(88)90017-X_BIB30","first-page":"99","article-title":"An O(n log n) Manhattan path algorithm","volume":"19","author":"Lipski","year":"1984"},{"key":"10.1016\/0167-9260(88)90017-X_BIB31","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1145\/359156.359164","article-title":"An algorithm for planning collision\u2014free paths among polyhedral obstacles","volume":"22","author":"Lozano-Perez","year":"1979","journal-title":"Comm. ACM"},{"key":"10.1016\/0167-9260(88)90017-X_BIB32","first-page":"1475","article-title":"A computer program for optimal routing of printed circuit conductors","volume":"2","author":"Mikami","year":"1968"},{"key":"10.1016\/0167-9260(88)90017-X_BIB33","first-page":"285","article-title":"Shortest path through a maze","volume":"30","author":"Moore","year":"1959","journal-title":"Ann. Comput. Lab. Harvard university"},{"key":"10.1016\/0167-9260(88)90017-X_BIB34","first-page":"71","article-title":"Shortest paths in the plane with convex polygonal obstacles","volume":"23","author":"Rohnert","year":"1986"},{"issue":"9","key":"10.1016\/0167-9260(88)90017-X_BIB35","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1109\/T-C.1974.224054","article-title":"The Lee path connection algorithm","volume":"C-23","author":"Rubin","year":"1974","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0167-9260(88)90017-X_BIB36","series-title":"Proc. 16th Annual Symp. Theory of Computation","first-page":"144","article-title":"On the shortest path in polyhedral spaces","author":"Sharir","year":"1984"},{"key":"10.1016\/0167-9260(88)90017-X_BIB37","first-page":"1281","article-title":"Circuit layout","volume":"69","author":"Soukup","year":"1981"},{"article-title":"Alternative Techniques for Modelling Travel Distance","year":"1974","author":"Vacarro","key":"10.1016\/0167-9260(88)90017-X_BIB38"},{"issue":"2","key":"10.1016\/0167-9260(88)90017-X_BIB39","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/0196-6774(82)90016-5","article-title":"Rectilinear line segment intersection layered segment trees, and dynamization","volume":"3","author":"Vaishnavi","year":"1982","journal-title":"J. Algorithms"},{"key":"10.1016\/0167-9260(88)90017-X_BIB40","doi-asserted-by":"crossref","first-page":"46","DOI":"10.5957\/jsr.1974.18.1.46","article-title":"Minimum-trajectory pipe routing","volume":"18","author":"Wangdahl","year":"1974","journal-title":"J. Ship Research"},{"key":"10.1016\/0167-9260(88)90017-X_BIB41","first-page":"167","article-title":"Constructing the visibility graph for n line segments in O(n2) time","volume":"20","author":"Welzi","year":"1985"},{"key":"10.1016\/0167-9260(88)90017-X_BIB42","doi-asserted-by":"crossref","unstructured":"Whitesides, S.H., Computational geometry and motion planning in: G.T. Toussaint, Ed., Computational Geometry (North-Holland, Amsterdam, 377\u2013427).","DOI":"10.1016\/B978-0-444-87806-9.50019-0"},{"key":"10.1016\/0167-9260(88)90017-X_BIB43","series-title":"Proc. WG'85, Internat. Confer. Graphtheoretic Concepts in Computer Science","first-page":"409","article-title":"Rectilinear shortest paths and minimum spanning trees with rectilinear barriers","author":"Wu","year":"1985"},{"key":"10.1016\/0167-9260(88)90017-X_BIB44","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF00289500","article-title":"A faster approximation algorithm for the Steiner problem in graphs","volume":"23","author":"Wu","year":"1986","journal-title":"Acta Informatica"}],"container-title":["Integration"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:016792608890017X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:016792608890017X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:37:03Z","timestamp":1757453823000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/016792608890017X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,5]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1988,5]]}},"alternative-id":["016792608890017X"],"URL":"https:\/\/doi.org\/10.1016\/0167-9260(88)90017-x","relation":{},"ISSN":["0167-9260"],"issn-type":[{"type":"print","value":"0167-9260"}],"subject":[],"published":{"date-parts":[[1988,5]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Optimal two-terminal \u03b1-\u03b2 wire routing","name":"articletitle","label":"Article Title"},{"value":"Integration","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/0167-9260(88)90017-X","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"converted-article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 1988 Published by Elsevier B.V.","name":"copyright","label":"Copyright"}]}}