{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:34:59Z","timestamp":1769974499065,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1991,6,1]],"date-time":"1991-06-01T00:00:00Z","timestamp":675734400000},"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":[[1991,6]]},"DOI":"10.1007\/bf01759042","type":"journal-article","created":{"date-parts":[[2005,6,16]],"date-time":"2005-06-16T10:43:56Z","timestamp":1118918636000},"page":"207-221","source":"Crossref","is-referenced-by-count":9,"title":["AnO(n logn) plane-sweep algorithm forL 1 andL \u221e Delaunay triangulations"],"prefix":"10.1007","volume":"6","author":[{"given":"Gary M.","family":"Shute","sequence":"first","affiliation":[]},{"given":"Linda L.","family":"Deneen","sequence":"additional","affiliation":[]},{"given":"Clark D.","family":"Thomborson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"BF01759042_CR1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/3166.315010","volume":"28","author":"J. Bentley","year":"1985","unstructured":"J. Bentley. Programming pearls.Communications of ACM,28(3):245\u2013250, March 1985.","journal-title":"Communications of ACM"},{"key":"BF01759042_CR2","doi-asserted-by":"crossref","unstructured":"M. W. Bern. Two probabilistic results on rectilinear Steiner trees. InProceedings of the 18th Annual ACM Symposium on the Theory of Computing, pages 433\u2013441, May 1986.","DOI":"10.1145\/12130.12175"},{"key":"BF01759042_CR3","doi-asserted-by":"crossref","unstructured":"L. P. Chew. There is a planer graph almost as good as the complete graph. InProceedings of the 2nd Annual Symposium on Computational Geometry, pages 169\u2013177, 1986.","DOI":"10.1145\/10515.10534"},{"key":"BF01759042_CR4","doi-asserted-by":"crossref","unstructured":"L. P. Chew and R. L. Drysdale. Voronoi diagrams based on convex distance functions. InProceedings of the Symposium on Computational Geometry, pages 235\u2013244, 1985","DOI":"10.1145\/323233.323264"},{"key":"BF01759042_CR5","doi-asserted-by":"crossref","unstructured":"R. A, Dwyer. A simple divide-and-conquer algorithm for constructing Delaunay triangulations inO(n log logn) expected time. InProceedings of the 2nd Annual Symposium on Computational Geometry, pages 276\u2013284, 1986.","DOI":"10.1145\/10515.10545"},{"key":"BF01759042_CR6","first-page":"189","volume-title":"Lecture Notes in Computer Science, vol. 194","author":"S. J. Fortune","year":"1985","unstructured":"S. J. Fortune. A fast algorithm for polygon containment by translation. InAutomata, Languages, and Programming, 12th Colloquium, Lecture Notes in Computer Science, vol. 194, pages 189\u2013198, Springer-Verlag, Berlin, 1985."},{"key":"BF01759042_CR7","doi-asserted-by":"crossref","unstructured":"S. J. Fortune. A sweepline algorithm for Voronoi diagrams. InProceedings of the 2nd Annual Symposium on Computational Geometry, pages 313\u2013319, 1986.","DOI":"10.1145\/10515.10549"},{"issue":"22","key":"BF01759042_CR8","first-page":"73","volume":"21","author":"P. J. Green","year":"1981","unstructured":"P. J. Green and R. Sibson. Computing Dirichlet tesselations in the plane.Computer Journal,21(22):73\u201387, 1981.","journal-title":"Computer Journal"},{"issue":"2","key":"BF01759042_CR9","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L. J. Guibas","year":"1985","unstructured":"L. J. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams.ACM Transactions on Graphics,4(2):74\u2013123, April 1985.","journal-title":"ACM Transactions on Graphics"},{"issue":"2","key":"BF01759042_CR10","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"F. K. Hwang","year":"1979","unstructured":"F. K. Hwang. AnO(n logn) algorithm for rectilinear minimal spanning trees.Journal of the ACM,26(2):177\u2013182, April 1979.","journal-title":"Journal of the ACM"},{"issue":"1","key":"BF01759042_CR11","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, AnO(n logn) algorithm for suboptimal rectilinear Steiner trees.IEEE Transactions on Circuits and Systems,26(1):75\u201377, January 1979.","journal-title":"IEEE Transactions on Circuits and Systems"},{"issue":"4","key":"BF01759042_CR12","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/322217.322219","volume":"27","author":"D. T. Lee","year":"1980","unstructured":"D. T. Lee. Two-dimensional Voronoi diagrams in theL p -metric.Journal of the ACM,27(4):604\u2013618, October 1980.","journal-title":"Journal of the ACM"},{"key":"BF01759042_CR13","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/0031-3203(85)90023-8","volume":"18","author":"D. T. Lee","year":"1985","unstructured":"D. T. Lee. Relative neighborhood graphs in theL 1-metric.Pattern Recognition,18:327\u2013332, 1985.","journal-title":"Pattern Recognition"},{"issue":"1","key":"BF01759042_CR14","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1137\/0210006","volume":"10","author":"D. T. Lee","year":"1981","unstructured":"D. T. Lee and R. L. Drysdale, III. Generalization of Voronoi diagrams in the plane.SIAM Journal of Computing,10(1):73\u201387, February 1981.","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"BF01759042_CR15","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF00977785","volume":"9","author":"D. T. Lee","year":"1980","unstructured":"D. T. Lee and B. J. Schachter. Two algorithms for constructing a Delaunay triangulation.International Journal of Computer and Information Sciences,9(3):219\u2013242, 1980.","journal-title":"International Journal of Computer and Information Sciences"},{"key":"BF01759042_CR16","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1137\/0209017","volume":"9","author":"D. T. Lee","year":"1980","unstructured":"D. T. Lee and C. K. Wong. Voronoi diagrams inL 1 (L \u221e) metrics with 2-dimensional storage applications.SIAM Journal of Computing,9:200\u2013211, 1980.","journal-title":"SIAM Journal of Computing"},{"issue":"7","key":"BF01759042_CR17","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1109\/TCS.1976.1084243","volume":"23","author":"J. H. Lee","year":"1976","unstructured":"J. H. Lee, N. K. Bose, and F. K. Hwang. Use of Steiner's problem in suboptimal routing in rectilinear metric.IEEE Transactions on Circuits and Systems,23(7):470\u2013476, July 1976.","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"BF01759042_CR18","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0020-0190(86)90038-4","volume":"22","author":"A. Lingas","year":"1986","unstructured":"A. Lingas. The greedy and Delaunay triangulations are not bad in the average case.Information Processing Letters,22:25\u201331, 1986.","journal-title":"Information Processing Letters"},{"key":"BF01759042_CR19","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01937482","volume":"24","author":"A. Maus","year":"1984","unstructured":"A. Maus. Delaunay triangulations and the convex hull ofn points in expected linear time.BIT,24:151\u2013163, 1984.","journal-title":"BIT"},{"key":"BF01759042_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos.Computational Geometry: An Introduction. Springer-Verlag, New York, 1985."},{"key":"BF01759042_CR21","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey. Closest point problems. InProceedings of the 16th IEEE Symposium on Foundations of Computer Science, pages 151\u2013162, 1975.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF01759042_CR22","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1080\/03052158008902421","volume":"4","author":"J. M. Smith","year":"1980","unstructured":"J. M. Smith, D. T. Lee, and J. S. Liebman. AnO(n logn) heuristic algorithm for the rectilinear Steiner minimal tree problem.Engineering Optimization,4:179\u2013192, 1980.","journal-title":"Engineering Optimization"},{"issue":"3","key":"BF01759042_CR23","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 minimal spanning trees.Journal of the ACM,30(3):428\u2013448, July 1983.","journal-title":"Journal of the ACM"},{"key":"BF01759042_CR24","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 neighbourhood graph of a finite planar set.Pattern Recognition,12:261\u2013268, 1980.","journal-title":"Pattern Recognition"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759042.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01759042\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01759042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T19:27:10Z","timestamp":1586287630000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01759042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,6]]},"references-count":24,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1991,6]]}},"alternative-id":["BF01759042"],"URL":"https:\/\/doi.org\/10.1007\/bf01759042","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,6]]}}}