{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T21:55:12Z","timestamp":1768686912400,"version":"3.49.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1984,6,1]],"date-time":"1984-06-01T00:00:00Z","timestamp":454896000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["BIT"],"published-print":{"date-parts":[[1984,6]]},"DOI":"10.1007\/bf01937482","type":"journal-article","created":{"date-parts":[[2005,7,31]],"date-time":"2005-07-31T05:58:23Z","timestamp":1122789503000},"page":"151-163","source":"Crossref","is-referenced-by-count":53,"title":["Delaunay triangulation and the convex hull ofn points in expected linear time"],"prefix":"10.1007","volume":"24","author":[{"given":"Arne","family":"Maus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01937482_CR1","unstructured":"A. Aho, J. Hopcroft and J. Ullman,The Design and Analysis of Computer Algorithms, (Addison-Wesley, 1974)."},{"key":"BF01937482_CR2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934391","volume":"22","author":"S. G. Akl","year":"1982","unstructured":"S. G. Akl,A constant-time parallel algorithm for computing convex hulls, BIT 22 (1982), 2.","journal-title":"BIT"},{"key":"BF01937482_CR3","doi-asserted-by":"crossref","unstructured":"K. E. Brassel and D. Reif,A procedure to generate Thiessen polygons, Geograph. Analys. 11, No. 3, July 1979.","DOI":"10.1111\/j.1538-4632.1979.tb00695.x"},{"key":"BF01937482_CR4","unstructured":"B. Delaunay,Sur la sphere vide, Bull. Acad. Sci. USSR(VII), Classe Sci. Mat. Nat., (1934), p. 793\u2013800."},{"key":"BF01937482_CR5","first-page":"4","volume":"3","author":"W. F. Eddy","year":"1977","unstructured":"W. F. Eddy,A new convex hull algorithm for planar set, ACM Trans. on Math. Softw. 3, (1977), 4.","journal-title":"ACM Trans. on Math. Softw."},{"key":"BF01937482_CR6","unstructured":"R. J. Fowler,Deltri. A program for inductively computing Delaunay triangulations, Tech. rep. no. 18, Geogr. Data Struct. Project., Dep. of Geogr., Simon Fraser Univ., Durnaby, British Columbia."},{"key":"BF01937482_CR7","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham,An efficient algorithm for determining the convex hull of a finite planar set, Inf. Proc. Letters, vol. 1, (1972), p. 132\u2013133.","journal-title":"Inf. Proc. Letters"},{"key":"BF01937482_CR8","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1093\/comjnl\/21.2.168","volume":"21","author":"P. J. Green","year":"1978","unstructured":"P. J. Green and R. Sibson,Computing Dirichlet tessellation in the plane, The Comp. J. 21, (1978), 168\u2013173.","journal-title":"The Comp. J."},{"key":"BF01937482_CR9","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 the Lp-metric, Journ. ACM 27, (1980) 604\u2013618.","journal-title":"Journ. ACM"},{"key":"BF01937482_CR10","first-page":"3","volume":"9","author":"D. T. Lee","year":"1980","unstructured":"D. T. Lee and B. J. Schachter,Two algorithms for constructing a Delaunay trinagulation, Int. J. of Comp. and Inf. Sci. 9, (1980), 3.","journal-title":"Int. J. of Comp. and Inf. Sci."},{"key":"BF01937482_CR11","doi-asserted-by":"crossref","unstructured":"M. J. McCullagh and C. G. Ross,Delaunay triangulation of a random set of data for isarithmic mapping, Cartogr. J., Dec. 1980.","DOI":"10.1179\/caj.1980.17.2.93"},{"key":"BF01937482_CR12","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1111\/j.2517-6161.1977.tb01615.x","volume":"B39","author":"B. D. Ripley","year":"1977","unstructured":"B. D. Ripley,Modelling spatial patterns, J. Roy. Stat. Soc. B39, (1977), p. 172\u2013192.","journal-title":"J. Roy. Stat. Soc."},{"key":"BF01937482_CR13","unstructured":"M. I. Shamos and J. L. Bentley,Optimal algorithms for structuring geographic data, in:An advanced study symposium on topological data structures for geographic information systems, Lab. for Comp. Graphics and Spat. Analys., Harvard Univ., Oct. 1977."},{"key":"BF01937482_CR14","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey,Closest-point problems, Proc. of the Sixteenth Symp. of Found. of Comp. Sci., IEEE, Oct. 1975.","DOI":"10.1109\/SFCS.1975.8"},{"key":"BF01937482_CR15","first-page":"14","volume":"7","author":"R. Sibson","year":"1980","unstructured":"R. Sibson,The Dirichlet tessalation as an aid in data analysis, Scand. J. Stat. 7, (1980), p. 14\u201320.","journal-title":"Scand. J. Stat."},{"key":"BF01937482_CR16","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, The Comp. J. 21, (1978), 243\u2013245.","journal-title":"The Comp. J."}],"container-title":["BIT"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01937482.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01937482\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01937482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T21:06:10Z","timestamp":1735851970000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01937482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984,6]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1984,6]]}},"alternative-id":["BF01937482"],"URL":"https:\/\/doi.org\/10.1007\/bf01937482","relation":{},"ISSN":["0006-3835","1572-9125"],"issn-type":[{"value":"0006-3835","type":"print"},{"value":"1572-9125","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,6]]}}}