{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T06:54:52Z","timestamp":1747810492011},"publisher-location":"Berlin\/Heidelberg","reference-count":24,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540528261"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032048","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"414-431","source":"Crossref","is-referenced-by-count":39,"title":["Randomized incremental construction of delaunay and Voronoi diagrams"],"prefix":"10.1007","author":[{"given":"Leonidas J.","family":"Guibas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donald E.","family":"Knuth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","unstructured":"G. Andrews, The Theory of Partitions, Addison-Wesley, 1976. (Encyclopedia of Mathematics and its Applications, Volume 2.)"},{"key":"32_CR2","first-page":"536","volume":"6","author":"J. Bentley","year":"1980","unstructured":"J. Bentley, B. Weide, and A. Yao, Optimal expected time algorithms for closest point problems, ACM Trans. Math. Soft. 6 (1980), 536\u2013580.","journal-title":"ACM Trans. Math. Soft."},{"key":"32_CR3","doi-asserted-by":"crossref","unstructured":"J-D. Boissonnat, and M. Teillaud, A hierarchical representation of objects: the Delaunay tree, Proc. 2nd ACM Symp. on Computational Geometry (1986), 260\u2013268.","DOI":"10.1145\/10515.10543"},{"key":"32_CR4","unstructured":"P. Chew, The simplest Voronoi diagram algorithm takes linear expected time, manuscript, 1988."},{"key":"32_CR5","unstructured":"K. Clarkson, Personal communication, 1989."},{"key":"32_CR6","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. Clarkson","year":"1989","unstructured":"K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II, Discrete Comp. Geom., 4 (1989), 387\u2013421.","journal-title":"Discrete Comp. Geom."},{"key":"32_CR7","first-page":"793","volume":"7","author":"B. Delaunay","year":"1934","unstructured":"B. Delaunay, Sur la sph\u00e8re vide, Izv. Akad. Nauk SSSR. Otdelenie Matematicheskii i Estestvennyka Nauk, 7 (1934), 793\u2013800.","journal-title":"Izv. Akad. Nauk SSSR. Otdelenie Matematicheskii i Estestvennyka Nauk"},{"key":"32_CR8","first-page":"109","volume":"84","author":"B. Delaunay","year":"1932","unstructured":"B. Delaunay, Neue Darstellung der geometrischen Krystallographie, Zeitschr. Krystallographie, 84 (1932), 109\u2013149.","journal-title":"Zeitschr. Krystallographie"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"R. Dwyer, Higher dimensional Voronoi diagrams in linear expected time, Proc. 5th ACM Symp. on Computational Geometry, 1989, 326\u2013333.","DOI":"10.1145\/73833.73869"},{"key":"32_CR10","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 1987."},{"key":"32_CR11","first-page":"371","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision, SIAM J. Comp. 15 (1986), 371\u2013340.","journal-title":"SIAM J. Comp."},{"key":"32_CR12","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 Voronoi diagrams, Algorithmica 2 (1987), 153\u2013174.","journal-title":"Algorithmica"},{"key":"32_CR13","unstructured":"S. Fortune, A note on Delaunay diagonal flips, unpublished manuscript."},{"key":"32_CR14","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1093\/comjnl\/21.2.168","volume":"21","author":"P. Green","year":"1977","unstructured":"P. Green and R. Sibson, Computing Dirichlet tesselation in the plane, Comput. J. 21 (1977), 168\u2013173.","journal-title":"Comput. J."},{"key":"32_CR15","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 Voronoi diagrams, ACM Trans. on Graphics 4 (1985), 74\u2013123.","journal-title":"ACM Trans. on Graphics"},{"key":"32_CR16","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"D. Kirkpatrick, Optimal search in planar subdivisions, SIAM J. Comp. 12 (1983), 28\u201335.","journal-title":"SIAM J. Comp."},{"key":"32_CR17","unstructured":"J. Jaromczyk, and G. Swiatek, Degenerate cases do not require more memory, manuscript, 1989."},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, S. Meiser and C. \u00d3'D\u00fanlaing, On the construction of abstract Voronoi diagrams, manuscript, 1989.","DOI":"10.1007\/3-540-52282-4_46"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, A fast planar partition algorithm, U. of Chicago, Dept. of Comp. Sc., Tech. Rep. 88-107, May 1988.","DOI":"10.1109\/SFCS.1988.21974"},{"key":"32_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry \u2014 An Introduction","author":"F. Preparata","year":"1985","unstructured":"F. Preparata and M. Shamos, Computational Geometry \u2014 An Introduction, Springer-Verlag, Berlin 1985."},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"F. Preparata and R. Tamassia, Fully dynamic techniques for point location and transitive closure in planar structures, Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, 558\u2013567.","DOI":"10.1109\/SFCS.1988.21972"},{"key":"32_CR22","unstructured":"R. Seidel, private communication."},{"key":"32_CR23","first-page":"97","volume":"133","author":"G. Voronoi","year":"1907","unstructured":"G. Voronoi, Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiques. Premier M\u00e9moire: Sur quelques propriete\u00e9s des formes quadratiques positives parfaites, J. reine angew. Math., 133 (1907), 97\u2013178.","journal-title":"J. reine angew. Math."},{"key":"32_CR24","first-page":"167","volume":"134","author":"G. Voronoi","year":"1908","unstructured":"G. Voronoi, Nouvelles applications des param\u00e8tres continus \u00e0 la th\u00e9orie des formes quadratiques. Deuxi\u00e8me M\u00e9moire: Recherches sur les parall\u00e9llo\u00e8dres primitifis, J. reine angew. Math., 134 (1908), 167\u2013171.","journal-title":"J. reine angew. Math."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0032048","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T21:19:50Z","timestamp":1683321590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032048"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0032048","relation":{},"subject":[]}}