{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:20:54Z","timestamp":1725456054850},"publisher-location":"Berlin\/Heidelberg","reference-count":16,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540543430"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028249","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T05:52:14Z","timestamp":1132638734000},"page":"42-53","source":"Crossref","is-referenced-by-count":3,"title":["Fully dynamic delaunay triangulation in logarithmic expected time per operation"],"prefix":"10.1007","author":[{"given":"Olivier","family":"Devillers","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Meiser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monique","family":"Teillaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02187749","volume":"4","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, L. Guibas, J. Saxe, and P. Shor. A linear time algorithm for computing the Vorono\u00ef diagram of a convex polygon. Discr. and Comp. Geom., 4:591\u2013604, 1989.","journal-title":"Discr. and Comp. Geom."},{"key":"6_CR2","unstructured":"J. Boissonnat, O. Devillers, R. Schott, M. Teillaud, and M. Yvinec. Applications of random sampling to on-line algorithms in computational geometry. Discr. and Comp. Geom. To be published. Full paper available as Technical Report INRIA 1285. Abstract published in IMACS 91 in Dublin."},{"key":"6_CR3","unstructured":"J. Boissonnat, O. Devillers, and M. Teillaud. A semi-dynamic construction of higher order Vorono\u00ef diagrams and its randomized analysis. Algorithmica. To be published. Full paper available as Technical Report INRIA 1207. Abstract published in Second Canadian Conference on Computational Geometry 1990 in Ottawa."},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"J. Boissonnat and M. Teillaud. A hierarchical representation of objects: the Delaunay Tree. In ACM Symp. on Comp. Geom., Jun. 1986.","DOI":"10.1145\/10515.10543"},{"key":"6_CR5","unstructured":"J. Boissonnat and M. Teillaud. On the randomized construction of the Delaunay tree. Theor. Comp. Sc. To be published. Full paper available as Technical Report INRIA 1140."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"K. Clarkson and P. Shor. Applications of random sampling in computational geometry, II. Discr. and Comp. Geom., 4(5), 1989.","DOI":"10.1007\/BF02187740"},{"key":"6_CR7","unstructured":"O. Devillers, S. Meiser, and M. Teillaud. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Technical Report 1349, INRIA, Dec. 1990."},{"key":"6_CR8","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S. Fortune","year":"1987","unstructured":"S. Fortune. A sweepline algorithm for Vorono\u00ef diagrams. Algorithmica, 2:153\u2013174, 1987.","journal-title":"Algorithmica"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"P. Green and R. Sibson. Computing Dirichlet tesselations in the plane. The Computer J., 21, 1978.","DOI":"10.1093\/comjnl\/21.2.168"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"L. Guibas, D. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Vorono\u00ef diagrams. In ICALP 90, pages 414\u2013431, Springer-Verlag, Jul. 1990.","DOI":"10.1007\/BFb0032048"},{"issue":"2","key":"6_CR11","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L. Guibas","year":"1985","unstructured":"L. Guibas and J. Stolfi. Primitives for the manipulation of general subdivisions and the computation of Vorono\u00ef diagrams. ACM Trans. on Graphics, 4(2):74\u2013123, Apr. 1985.","journal-title":"ACM Trans. on Graphics"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"D. Lee and B. Schacter. Two algorithms for constructing a Delaunay triangulation. International Journal of Computer and Information Sciences, 9(3), 1980.","DOI":"10.1007\/BF00977785"},{"key":"6_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. \u00d3'D\u00fanlaing. On the construction of abstract Vorono\u00ef diagrams. Discr. and Comp. Geom., 6:211\u2013224, 1991.","journal-title":"Discr. and Comp. Geom."},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"K. Mulmuley. On levels in arrangements and Vorono\u00ef diagrams. Discr. and Comp. Geom. To be published.","DOI":"10.1007\/BF02574692"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"F. Preparata and M. Shamos. Computational Geometry: an Introduction. Springer-Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"6_CR16","volume-title":"Computational Geometry","author":"M. Shamos","year":"1978","unstructured":"M. Shamos. Computational Geometry. PhD thesis, Department of Computer Science, Yale University, (USA), 1978."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028249.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:58:30Z","timestamp":1607551110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028249"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540543430"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/bfb0028249","relation":{},"subject":[]}}