{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:33:18Z","timestamp":1772519598541,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1993,4,1]],"date-time":"1993-04-01T00:00:00Z","timestamp":733622400000},"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":[[1993,4]]},"DOI":"10.1007\/bf01228508","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T19:18:45Z","timestamp":1109359125000},"page":"329-356","source":"Crossref","is-referenced-by-count":24,"title":["A semidynamic construction of higher-order voronoi diagrams and its randomized analysis"],"prefix":"10.1007","volume":"9","author":[{"given":"Jean -Daniel","family":"Boissonnat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olivier","family":"Devillers","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monique","family":"Teillaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"J. D. Boissonnat and M. Teillaud. A hierarchical representation of objects: the Delaunay Tree. InProceedings of the Second ACM Symposium on Computational Geometry, Yorktown Heights, pp. 260?268, June 1986.","DOI":"10.1145\/10515.10543"},{"key":"CR2","unstructured":"J. D. Boissonnat and M. Teillaud. On the randomized construction of the Delaunay tree.Theoretical Computer Science. To be published. Full paper available as Technical Report INRIA 1140."},{"key":"CR3","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, pp. 151?162, October 1975.","DOI":"10.1109\/SFCS.1975.8"},{"key":"CR4","first-page":"478","volume":"31","author":"D. T. Lee","year":"1982","unstructured":"D. T. Lee. Onk-nearest neighbor Voronoi diagrams in the plane.IEEE Transactions on Computers, 31:478?487, 1982.","journal-title":"IEEE Transactions on Computers"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor. A linear-time algorithm for computing the Voronoi diagram of a convex polygon.Discrete and Computational Geometry, 4:591?604, 1989.","journal-title":"Discrete and Computational Geometry"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"B. Chazelle and H. Edelsbrunner. An improved algorithm for constructingkth-order Voronoi diagrams. InProceedings of the First ACM Symposium on Computational Geometry, Baltimore, pp. 228?234, June 1985.","DOI":"10.1145\/323233.323263"},{"key":"CR7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. L. Clarkson","year":"1987","unstructured":"K. L. Clarkson. New applications of random sampling in computational geometry.Discrete and Computational Geometry, 2:195?222, 1987.","journal-title":"Discrete and Computational Geometry"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF01758770","volume":"7","author":"L. J. Guibas","year":"1992","unstructured":"L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams.Algorithmica, 7:381?413, 1992.","journal-title":"Algorithmica"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF02574686","volume":"6","author":"K. Mehlhorn","year":"1991","unstructured":"K. Mehlhorn, S. Meiser, and C. \u00d3'Dunlaing. On the construction of abstract Voronoi diagrams.Discrete and Computational Geometry, 6:211?224, 1991.","journal-title":"Discrete and Computational Geometry"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. L. Clarkson","year":"1989","unstructured":"K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete and Computational Geometry, 4:387?421, 1989.","journal-title":"Discrete and Computational Geometry"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. On obstruction in relation to a fixed viewpoint. InProceedings of the 30th IEEE Symposium on Foundations of Computer Science, pp. 592?597, 1989.","DOI":"10.1109\/SFCS.1989.63540"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02574694","volume":"6","author":"R. A. Dwyer","year":"1991","unstructured":"R. A. Dwyer. Higher-dimensional Voronoi diagrams in linear expected time.Discrete and Computational Geometry, 6:343?367, 1991.","journal-title":"Discrete and Computational Geometry"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM Journal on Computing, 15:341?363, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF02574692","volume":"6","author":"K. Mulmuley","year":"1991","unstructured":"K. Mulmuley. On levels in arrangements and Voronoi diagrams.Discrete and Computational Geometry, 6:307?338, 1991.","journal-title":"Discrete and Computational Geometry"},{"key":"CR15","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":"CR16","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 tesselations in the plane.The Computer Journal, 21:168?173, 1978.","journal-title":"The Computer Journal"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02293035","volume":"8","author":"J. D. Boissonnat","year":"1992","unstructured":"J. D. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of Random Sampling to On-line Algorithms in Computational Geometry.Discrete and Computational Geometry, 8:51?71, 1992.","journal-title":"Discrete and Computational Geometry"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01228508.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01228508\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01228508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T23:35:52Z","timestamp":1586129752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01228508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,4]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,4]]}},"alternative-id":["BF01228508"],"URL":"https:\/\/doi.org\/10.1007\/bf01228508","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,4]]}}}