{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:36:06Z","timestamp":1742384166091},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1994,12,1]],"date-time":"1994-12-01T00:00:00Z","timestamp":786240000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,12]]},"DOI":"10.1007\/bf01188713","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T10:55:44Z","timestamp":1108724144000},"page":"421-435","source":"Crossref","is-referenced-by-count":7,"title":["Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors"],"prefix":"10.1007","volume":"12","author":[{"given":"Y. C.","family":"Wee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Chaiken","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01762120","volume":"3","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal, B. Chazelle, L. Guibas, C. \u00d3'D\u00fanlaing, and C. Yap, Parallel Computational Geometry,Algorithmica,3 (1988), 293?327.","journal-title":"Algorithmica"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"M. J. Atallah, R. Cole, and M. T. Goodrich, Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms,Proc. 28th IEEE Symp. on Foundations of Computer Science, 1987, pp. 151?160.","DOI":"10.1109\/SFCS.1987.12"},{"key":"CR3","volume-title":"Ph.D. Thesis MIT\/LCS\/TR-248","author":"A. Baratz","year":"1983","unstructured":"A. Baratz, Algorithms for Integrated Circuit Signal Routing, Ph.D. Thesis MIT\/LCS\/TR-248, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1983."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley, Decomposable Searching Problems,Inform. Process. Lett.,8 (1979), 244?251.","journal-title":"Inform. Process. Lett."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley, Multidimensional Divide and Conquer,Comm. ACM,23 (1980), 214?229.","journal-title":"Comm. ACM"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01762114","volume":"3","author":"M. W. Bern","year":"1988","unstructured":"M. W. Bern, Two Probabilistic Results on Rectilinear Steiner Trees,Algorithmica,3 (1988), 191?204.","journal-title":"Algorithmica"},{"key":"CR7","volume-title":"Technical Report No. UCB-CSD-87-306","author":"M. W. Bern","year":"1986","unstructured":"M. W. Bern and M. de Carvalho, A Greedy Heuristic for the Rectilinear Steiner Tree Problem, Technical Report No. UCB-CSD-87-306, Computer Science Division, University of California, Berkeley, CA, 1986."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"B. Chazelle and B. Rosenburg, Computing Partial Sums in Multidimensional Arrays,Proc. 5th Ann. ACM Symp. on Computational Geometry, 1989, pp. 131?139.","DOI":"10.1145\/73833.73848"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"K. Clarkson, Fast Expected-Time and Approximation Algorithms for Geometric Minimum Spanning Trees,Proc. 16th Ann. ACM Symp. on Theory of Computing, 1984, pp. 342?348.","DOI":"10.1145\/800057.808699"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"K. Clarkson, Approximation Problems for Shortest Path Motion Planning,Proc. 19th Ann. ACM Symp. on Theory of Computing, 1987, pp. 56?65.","DOI":"10.1145\/28395.28402"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1016\/0196-6774(85)90030-6","volume":"6","author":"H. Edelsbrunner","year":"1985","unstructured":"H. Edelsbrunner and M. H. Overmars, Batched Dynamic Solutions to Decomposable Searching Problems,J. Algorithms,6 (1985), 515?542.","journal-title":"J. Algorithms"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M. L. Fredman","year":"1987","unstructured":"M. L. Fredman and R. E. Tarjan, Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms,J. Assoc. Comput. Mach.,34 (1987), 596?615.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Fransisco, CA, 1979."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TCS.1979.1084551","volume":"26","author":"F. K. Hwang","year":"1979","unstructured":"F. K. Hwang, An0(n logn) Algorithm for Suboptimal Rectilinear Steiner Trees,IEEE Trans. Circuits and Systems,26 (1979), 75?77.","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230220105","volume":"22","author":"F. K. Hwang","year":"1992","unstructured":"F. K. Hwang and D. S. Richards, Steiner Tree Problems,Networks,22 (1992), 55?89.","journal-title":"Networks"},{"key":"CR16","volume-title":"Technical Report No. WUCS-89-11","author":"M. Imase","year":"1989","unstructured":"M. Imase and B. M. Waxman, Dynamic Steiner Tree Problem, Technical Report No. WUCS-89-11, Department of Computer Science, Washington University, St. Louis, MO, 1989."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"J. W. Jaromczyk and M. Kowaluk, A Note on Relative Neighborhood Graphs,Proc. Third Ann. Symp. on Computational Geometry, 1987, pp. 233?241.","DOI":"10.1145\/41958.41983"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF02247943","volume":"40","author":"J. Katajainen","year":"1988","unstructured":"J. Katajainen, The Region Approach for Computing Relative Neighborhood Graphs in theL p Metric,Computing,40 (1988), 147?161.","journal-title":"Computing"},{"key":"CR19","volume-title":"Parallel Algorithms for the Segment-Dragging Problem","author":"S. K. Kim","year":"1989","unstructured":"S. K. Kim, Parallel Algorithms for the Segment-Dragging Problem, Unpublished Manuscript, Department of Computer Science and Engineering, University of Washington, Seattle, WA, 1989."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01553886","volume":"4","author":"D. Richards","year":"1989","unstructured":"D. Richards, Fast Heuristic Algorithms for Rectilinear Steiner Trees,Algorithmica,4 (1989), 191?207.","journal-title":"Algorithmica"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1145\/2402.322386","volume":"30","author":"K. J. Supowit","year":"1983","unstructured":"K. J. Supowit, The Relative Neighborhood Graph with an Application to Minimum Spanning Trees,J. Assoc. Comput Mach.,30 (1983), 428?447.","journal-title":"J. Assoc. Comput Mach."},{"key":"CR22","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0031-3203(80)90066-7","volume":"12","author":"G. T. Toussaint","year":"1980","unstructured":"G. T. Toussaint, The Relative Neighborhood Graph of a Finite Planar Set,Pattern Recognition,12 (1980), 261?268.","journal-title":"Pattern Recognition"},{"key":"CR24","volume-title":"Ph.D. Thesis","author":"Y. C. Wee","year":"1989","unstructured":"Y. C. Wee, Efficient Algorithms for Proximity Problems, Ph.D. Thesis, Department of Computer Science, SUNY, Albany, NY, 1989."},{"key":"CR25","unstructured":"Y. C. Wee and S. Chaiken, An Optimal ParallelL 1 Metric Voronoi Diagram Algorithm,Proc. Second Canadian Conf. on Computational Geometry, 1990, pp. 60?65."},{"key":"CR26","unstructured":"Y. C. Wee, S. Chaiken, and S. S. Ravi, Some Applications of the Geographic Nearest Neighbors Approach,Proc. 27th Ann. Allerton Conf. on Communication, Control, and Computing, 1989, pp. 555?563."},{"key":"CR27","series-title":"Technical Report No. 88-31","volume-title":"First Canadian Conference on Computational Geometry, 1989","author":"Y. C. Wee","year":"1988","unstructured":"Y. C. Wee, S. Chaiken, and D. E. Willard, The Angle Restricted Voronoi Diagram,First Canadian Conference on Computational Geometry, 1989. (Also available as Technical Report No. 88-31, Department of Computer Science, SUNY, Albany, NY, 1988.)"},{"key":"CR28","first-page":"233","volume":"14","author":"D. E. Willard","year":"1985","unstructured":"D. E. Willard, New Data Structure for Orthogonal Range Queries,SIAM J. Comput.,14 (1985), 233?253.","journal-title":"SIAM J. Comput."},{"key":"CR29","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1145\/31846.42228","volume":"34","author":"D. E. Willard","year":"1987","unstructured":"D. E. Willard, Multidimensional Search Trees that Provides New Types of Memory Reductions,J. Assoc. Comput. Mach.,34 (1987), 845?858.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR30","doi-asserted-by":"crossref","unstructured":"D. E. Willard and Y. C. Wee, Quasi-Valid Range Querying and Its Implications for Nearest-Neighbor Problems,Proc. 4th Ann. ACM Symp. on Computational Geometry, 1988, pp. 34?43.","DOI":"10.1145\/73393.73398"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A. C. Yao","year":"1982","unstructured":"A. C. Yao, On Constructing Minimum Spanning Trees ink-Dimensional Spaces and Related Problems,SIAM J. Comput.,11 (1982), 721?736.","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188713.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01188713\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01188713","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T20:50:47Z","timestamp":1586119847000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01188713"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["BF01188713"],"URL":"https:\/\/doi.org\/10.1007\/bf01188713","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}