{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T12:22:21Z","timestamp":1770294141169,"version":"3.49.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1987,11,1]],"date-time":"1987-11-01T00:00:00Z","timestamp":562723200000},"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":[[1987,11]]},"DOI":"10.1007\/bf01840356","type":"journal-article","created":{"date-parts":[[2005,6,29]],"date-time":"2005-06-29T03:41:00Z","timestamp":1120016460000},"page":"137-151","source":"Crossref","is-referenced-by-count":154,"title":["A faster divide-and-conquer algorithm for constructing delaunay triangulations"],"prefix":"10.1007","volume":"2","author":[{"given":"Rex A.","family":"Dwyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01840356_CR1","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/355921.355927","volume":"6","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley, B. W. Weide, and A. C. Yao, Optimal expected-time algorithms for closest point problems,ACM Trans. Math. Software,6 (1980), 563\u2013580.","journal-title":"ACM Trans. Math. Software"},{"key":"BF01840356_CR2","first-page":"313","volume-title":"A sweepline algorithm for Voronoi diagrams","author":"S. Fortune","year":"1986","unstructured":"S. Fortune, A sweepline algorithm for Voronoi diagrams,Proceedings of the Second Annual Symposium on Computational Geometry, Yorktown Heights, NY, 1986, pp. 313\u2013322."},{"key":"BF01840356_CR3","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 Trans. Graphics,4 (1985), 74\u2013123.","journal-title":"ACM Trans. Graphics"},{"key":"BF01840356_CR4","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,J Assoc. Comput. Mach.,26 (1979), 177\u2013182.","journal-title":"J Assoc. Comput. Mach."},{"key":"BF01840356_CR5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/B978-0-12-587260-7.50011-X","volume-title":"Mathematical Software III","author":"C. L. Lawson","year":"1977","unstructured":"C. L. Lawson, Software forC 1 surface interpolation, inMathematical Software III (J. R. Rice, ed.), Academic Press, New York, 1977, pp. 161\u2013194."},{"key":"BF01840356_CR6","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,J. Assoc. Comput. Mach.,27 (1980), 604\u2013618.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01840356_CR7","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. Schachter, Two algorithms for constructing Delaunay triangulations,Internat. J. Comput. Inform. Sci.,9 (1980), 219\u2013242.","journal-title":"Internat. J. Comput. Inform. Sci."},{"key":"BF01840356_CR8","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 two-dimensional storage applications,SIAM J. Comput.,9, (1980), 200\u2013211.","journal-title":"SIAM J. Comput."},{"key":"BF01840356_CR9","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1093\/comjnl\/19.2.178","volume":"19","author":"D. H. McLain","year":"1976","unstructured":"D. H. McLain, Two-dimensional interpolation from random data,Comput. J.,19 (1976), 178\u2013181 and 384.","journal-title":"Comput. J."},{"key":"BF01840356_CR10","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF01937482","volume":"24","author":"A. Maus","year":"1984","unstructured":"A. Maus, Delaunay triangulation and the convex hull ofn points in expected linear time.BIT,24 (1984), 151\u2013163.","journal-title":"BIT"},{"key":"BF01840356_CR11","first-page":"306","volume":"27","author":"T. Ohya","year":"1984","unstructured":"T. Ohya, M. Iri, and K. Murota, Improvements of the incremental methods for the Voronoi diagram with computational comparison of various algorithms,J. Oper. Res. Soc. Japan,27 (1984), 306\u2013336.","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"BF01840356_CR12","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey, Closest-point problems,Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, 1976, pp. 208\u2013215.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF01840356_CR13","volume-title":"Computational Geometry: An Introduction","author":"M. I. Shamos","year":"1985","unstructured":"M. I. Shamos and F. P. Preparata,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985."},{"key":"BF01840356_CR14","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1093\/comjnl\/21.3.243","volume":"21","author":"R. Sibson","year":"1978","unstructured":"R. Sibson, Locally equiangular triangulations,Comput. J.,21 (1978), 243\u2013245.","journal-title":"Comput. J."},{"key":"BF01840356_CR15","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1093\/comjnl\/21.3.243","volume":"21","author":"R. Sibson","year":"1978","unstructured":"R. Sibson and P. J. Green, Computing Dirichlet tessellations in the plane,Comput. J.,21 (1978), 168\u2013173.","journal-title":"Comput. J."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840356.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840356\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840356","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T01:48:34Z","timestamp":1586310514000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840356"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,11]]},"references-count":15,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1987,11]]}},"alternative-id":["BF01840356"],"URL":"https:\/\/doi.org\/10.1007\/bf01840356","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,11]]}}}