{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T13:05:19Z","timestamp":1754485519893},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575689"},{"type":"electronic","value":"9783540482338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57568-5_231","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:09:32Z","timestamp":1330261772000},"page":"21-30","source":"Crossref","is-referenced-by-count":6,"title":["Remembering conflicts in history yields dynamic algorithms"],"prefix":"10.1007","author":[{"given":"Katrin","family":"Dobrindt","sequence":"first","affiliation":[]},{"given":"Mariette","family":"Yvinec","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"3_CR1","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":"3_CR2","unstructured":"J. D. Boissonnat and K. Dobrindt. Randomized construction of the upper envelope of triangles in IR3. In Proc. 4th Canad. Conf. Comput. Geom., pages 311\u2013315, 1992."},{"key":"3_CR3","unstructured":"J-D. Boissonnat and M. Yvinec. Structures et algorithmes g\u00e9om\u00e9triques. To appear, 1994."},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"K. L. Clarkson, K. Mehlhorn, and R. Seidel. Four results on randomized incremental constructions. In Proc. 9th Sympos. Theoret. Aspects Comput. Sci., volume 577 of Lecture Notes in Computer Science, pages 463\u2013474. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-55210-3_205"},{"key":"3_CR5","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":"3_CR6","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0925-7721(92)90025-N","volume":"2","author":"O. Devillers","year":"1992","unstructured":"O. Devillers, S. Meiser, and M. Teillaud. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Comput. Geom. Theory Appl., 2(2):55\u201380, 1992.","journal-title":"Comput. Geom. Theory Appl."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing \u2014 upper and lower bounds. In Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci., pages 524\u2013531, 1988.","DOI":"10.1109\/SFCS.1988.21968"},{"key":"3_CR8","volume-title":"Ph.D. thesis","author":"K. Dobrindt","year":"1994","unstructured":"K. Dobrindt. Ph.D. thesis, Ecole de Mines de Paris, Paris, France, 1994."},{"key":"3_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Heidelberg, West Germany, 1987."},{"key":"3_CR10","doi-asserted-by":"publisher","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":"3_CR11","volume-title":"Sorting and Searching, volume 1 of Data Structures and Algorithms","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Sorting and Searching, volume 1 of Data Structures and Algorithms. Springer-Verlag, Heidelberg, West Germany, 1984."},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0020-0190(90)90022-P","volume":"35","author":"K. Mehlhorn","year":"1990","unstructured":"K. Mehlhorn and S. N\u00e4her. Bounded ordered dictionaries in O(log log n) time and O(n) space. Inform. Process. Lett., 35:183\u2013189, 1990.","journal-title":"Inform. Process. Lett."},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. A fast planar partition algorithm, I. In Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci., pages 580\u2013589, 1988.","DOI":"10.1109\/SFCS.1988.21974"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Randomized multidimensional search trees: dynamic sampling. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 121\u2013131, 1991.","DOI":"10.1145\/109648.109662"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. Randomized multidimensional search trees: lazy balancing and dynamic shuffling. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 180\u2013196, 1991.","DOI":"10.1109\/SFCS.1991.185368"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"O. Schwarzkopf. Dynamic maintenance of geometric structures made easy. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 197\u2013206, 1991.","DOI":"10.1109\/SFCS.1991.185369"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57568-5_231.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:06Z","timestamp":1605647586000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57568-5_231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575689","9783540482338"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-57568-5_231","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}