{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T10:55:45Z","timestamp":1762340145137},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,10,1]],"date-time":"1995-10-01T00:00:00Z","timestamp":812505600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete & Computational Geometry"],"published-print":{"date-parts":[[1995,10]]},"DOI":"10.1007\/bf02570705","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T04:22:00Z","timestamp":1177734120000},"page":"261-286","source":"Crossref","is-referenced-by-count":38,"title":["On lazy randomized incremental construction"],"prefix":"10.1007","volume":"14","author":[{"given":"M.","family":"de Berg","sequence":"first","affiliation":[]},{"given":"K.","family":"Dobrindt","sequence":"additional","affiliation":[]},{"given":"O.","family":"Schwarzkopf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[1995,10,1]]},"reference":[{"issue":"2","key":"BF02570705_CR1","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF02123007","volume":"10","author":"B. Aronov","year":"1990","unstructured":"B. Aronov and M. Sharir. Triangles in space or building (and analyzing) castles in the air.Combinatorica, 10(2):137\u2013173, 1990.","journal-title":"Combinatorica"},{"key":"BF02570705_CR2","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 Comput. Geom., 8:51\u201371, 1992.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570705_CR3","unstructured":"J. D. Boissonnat and K. Dobrindt. Randomized construction of the upper envelope of triangles inR 3.Proc. 4th Canad. Conf. on Computational Geometry, pp. 311\u2013315, 1992."},{"key":"BF02570705_CR4","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/0304-3975(93)90024-N","volume":"112","author":"J.-D. Boissonnat","year":"1993","unstructured":"J.-D. Boissonnat and M. Teillaud. On the randomized construction of the Delaunay tree.Theoret. Comput. Sci., 112:339\u2013354, 1993.","journal-title":"Theoret. Comput. Sci."},{"key":"BF02570705_CR5","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir and J. Snoeyink. Computing a face in an arrangement of line segments.Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, pp. 441\u2013448, 1991."},{"key":"BF02570705_CR6","series-title":"Technical Report PCS-TR90-147","volume-title":"Building Voronoi Diagrams for Convex Polygons in Linear Expected Time","author":"L. P. Chew","year":"1986","unstructured":"L. P. Chew. Building Voronoi Diagrams for Convex Polygons in Linear Expected Time. Technical Report PCS-TR90-147, Department of Mathematics and Computer Science, Dartmouth College, Hanover, NH, 1986."},{"key":"BF02570705_CR7","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02187783","volume":"5","author":"K. Clarkson","year":"1990","unstructured":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl. Combinatorial complexity bounds for arrangements of curves and spheres.Discrete Comput. Geom., 5:99\u2013160, 1990.","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"BF02570705_CR8","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"K. L. Clarkson","year":"1993","unstructured":"K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions.Comput. Geom. Theory Appl., 3(4):185\u2013212, 1993.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF02570705_CR9","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 Comput. Geom. 4:387\u2013421, 1989.","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"BF02570705_CR10","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0222031","volume":"22","author":"H. Edelsbrunner","year":"1993","unstructured":"H. Edelsbrunner, R. Seidel, and M. Sharir. On the zone theorem for hyperplane arrangements.SIAM J. Comput., 22(2):418\u2013429, 1993.","journal-title":"SIAM J. Comput."},{"key":"BF02570705_CR11","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\u2013413, 1992.","journal-title":"Algorithmica"},{"key":"BF02570705_CR12","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/BF02187744","volume":"4","author":"L. J. Guibas","year":"1989","unstructured":"L. J. Guibas, M. Sharir, and S. Sifrony. On the general motion planning problem with two degrees of freedom.Discrete Comput. Geom., 4:491\u2013521, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570705_CR13","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. O'D\u00fanlaing. On the construction of abstract Voronoi diagrams.Discrete Comput. Geom., 6:211\u2013224, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570705_CR14","unstructured":"N. Miller and M. Sharir. Efficient randomized algorithm for constructing the union of fat triangles and of pseudodisks. Manuscript, 1991."},{"key":"BF02570705_CR15","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. A fast planar partition algorithm, I.Proc. 29th IEEE Symp. on Foundations of Computer Science, pp. 580\u2013589, 1988.","DOI":"10.1109\/SFCS.1988.21974"},{"key":"BF02570705_CR16","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1993","unstructured":"K. Mulmuley.Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, NJ, 1993."},{"key":"BF02570705_CR17","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF02187902","volume":"3","author":"R. Pollack","year":"1987","unstructured":"R. Pollack, M. Sharir, and S. Sifrony. Separating two simple polygons by a sequence of translations.Discrete Comput. Geom., 3:123\u2013136, 1987.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570705_CR18","volume-title":"Dynamic Maintenance of Convex Polytopes and Related Structures","author":"O. Schwarzkopf","year":"1992","unstructured":"O. Schwarzkopf. Dynamic Maintenance of Convex Polytopes and Related Structures. Ph.D. thesis, Fachbereich Mathematik, Freie Universit\u00e4t Berlin, Berlin, June 1992."},{"key":"BF02570705_CR19","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"R. Seidel. Small-dimensional linear programming and convex hulls made easy.Discrete Comput. Geom., 6:423\u2013434, 1991.","journal-title":"Discrete Comput. Geom."},{"key":"BF02570705_CR20","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-642-58043-7_3","volume-title":"New Trends in Discrete and Computational Geometry, vol. 10 ofAlgorithms and Combinatorics","author":"R. Seidel","year":"1993","unstructured":"R. Seidel. Backwards analysis of randomized geometric algorithms. In J. Pach, editor,New Trends in Discrete and Computational Geometry, vol. 10 ofAlgorithms and Combinatorics, pp. 37\u201368. Springer-Verlag, New York, 1993."},{"key":"BF02570705_CR21","doi-asserted-by":"crossref","unstructured":"B. Tagansky. A new technique for analyzing substructures in arrangements.Proc. 11th Annual ACM Symp. on Computational Geometry, pp. 200\u2013209, 1995.","DOI":"10.1145\/220279.220301"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02570705.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02570705\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02570705","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,18]],"date-time":"2019-05-18T15:59:43Z","timestamp":1558195183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02570705"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,10]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,10]]}},"alternative-id":["BF02570705"],"URL":"https:\/\/doi.org\/10.1007\/bf02570705","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,10]]}}}