{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T19:13:36Z","timestamp":1783106016592,"version":"3.54.6"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540551218","type":"print"},{"value":"9783540467359","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_11","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:47:41Z","timestamp":1330249661000},"page":"113-125","source":"Crossref","is-referenced-by-count":38,"title":["Voronoi diagrams of moving points in the plane"],"prefix":"10.1007","author":[{"given":"Leonidas J.","family":"Guibas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph S. B.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Roos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"S. Abramowski and H. M\u00fcller, Collision Avoidance for Nonrigid Objects, in H. Noltemeier (ed.): ZOR \u2014 Zeitschrift f\u00fcr Operations Research, Vol. 32, 1988, pp 165\u2013186","DOI":"10.1007\/BF01928919"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, L. Guibas, J. Saxe and P. Shor, A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon, Proc. of the 19th Annual ACM Symposium on Theory of Computing, New York City, 1987, pp 39\u201345","DOI":"10.1145\/28395.28400"},{"key":"11_CR3","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1016\/0097-3165(89)90032-0","volume":"52","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, M. Sharir and P. Shor, Sharp Upper and Lower Bounds on the Length of General Davenport-Schinzel Sequences, Journal of Combinatorial Theory, Series A, Vol. 52, 1989, pp 228\u2013274","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1016\/0898-1221(85)90105-1","volume":"11","author":"M.J. Atallah","year":"1985","unstructured":"M.J. Atallah, Some Dynamic Computational Geometry Problems, Computers and Mathematics with Applications, Vol. 11, 1985, pp 1171\u20131181","journal-title":"Computers and Mathematics with Applications"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"H. Aunuma, H. Imai, K. Imai and T. Tokuyama, Maximin Locations of Convex Objects and Related Dynamic Voronoi Diagrams, Proc. of the 6th ACM Symposium on Computational Geometry, Berkeley, 1990, pp 225\u2013234","DOI":"10.1145\/98524.98575"},{"key":"11_CR6","unstructured":"F. Aurenhammer, Voronoi Diagrams \u2014 A Survey, Report 263, Nov. 1988, Institute f\u00fcr Informationsverarbeitung, Techn. Univ. Graz"},{"issue":"No.11","key":"11_CR7","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1109\/TC.1987.5009474","volume":"C-36","author":"B. Chazelle","year":"1987","unstructured":"B. Chazelle and H. Edelsbrunner, An Improved Algorithm for Constructing k th-Order Voronoi Diagrams, IEEE Transactions on Computers, Vol. C-36, Nov. 1987, No. 11, pp 1349\u20131354","journal-title":"IEEE Transactions on Computers"},{"key":"11_CR8","unstructured":"R.L. Drysdale III and D.T. Lee, Generalized Voronoi Diagrams in the Plane, Proc. 16th Annual Allerton Conference on Communications, Control and Computing, Oct. 1978, pp 833\u2013842"},{"key":"11_CR9","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/BF01840438","volume":"1","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, Edge-Skeletons in Arrangements with Applications, Algorithmica 1986, Vol. 1, pp 93\u2013109","journal-title":"Algorithmica"},{"key":"11_CR10","volume-title":"EATCS Monographs in Computer Science","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs in Computer Science, Springer-Verlag, Berlin-Heidelberg, 1987"},{"issue":"No.2","key":"11_CR11","doi-asserted-by":"publisher","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 J. Comput., Vol. 15, No. 2, May 1986, pp 341\u2013363","journal-title":"SIAM J. Comput."},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"S. Fortune, A Sweep-line Algorithm for Voronoi Diagrams, Proc. 2nd Annual ACM Symp. Computational Geometry, Yorktown Heights, 1986, pp 313\u2013322","DOI":"10.1145\/10515.10549"},{"issue":"No.1","key":"11_CR13","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1142\/S0218195991000037","volume":"1","author":"J-J. Fu","year":"1991","unstructured":"J-J. Fu and R.C.T. Lee, Voronoi Diagrams of Moving Points in the Plane, Int. Journal of Computational Geometry & Applications, Vol. 1, No. 1, 1991, pp 23\u201332","journal-title":"Int. Journal of Computational Geometry & Applications"},{"key":"11_CR14","unstructured":"H. Imai and K. Imai, Voronoi Diagrams of Moving Points, Proc. Int. Computer Symp., Taiwan, 1990, pp 600\u2013606"},{"issue":"No.5","key":"11_CR15","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1109\/TIT.1983.1056738","volume":"IT-29","author":"I.G. Gowda","year":"1983","unstructured":"I.G. Gowda, D.G. Kirkpatrick, D.T. Lee and A. Naamad, Dynamic Voronoi Diagrams, IEEE Trans. on Information Theory, Vol. IT-29, No. 5, Sept. 1983, pp 724\u2013731","journal-title":"IEEE Trans. on Information Theory"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"L. Guibas, D.E. Knuth and M. Sharir, Randomized Incremental Construction of Delaunay and Voronoi Diagrams, Proc. 17th Intern. Colloquium on Automata, Languages and Programming ICALP 90, LNCS 443, Springer, 1990, pp 414\u2013431","DOI":"10.1007\/BFb0032048"},{"issue":"No.2","key":"11_CR17","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 Transactions on Graphics, Vol. 4, No. 2, April 1985, pp 74\u2013123","journal-title":"ACM Transactions on Graphics"},{"key":"11_CR18","unstructured":"H. Hadwiger und H. Debrunner, Kombinatorische Geometrie in der Ebene, Monographies de L'Enseignement Math\u00e9matique, No. 2, Universit\u00e9 Gen\u00e8ve, 1959"},{"key":"11_CR19","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel Sequences and of Generalized Path Compression Schemes, Combinatorica, 1986, Vol. 6, pp 151\u2013177","journal-title":"Combinatorica"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"K. Imai, S. Sumino and H. Imai, Geometric Fitting of Two Corresponding Sets of Points, Proc. 5th ACM Symp. on Computational Geometry, 1989, pp 266\u2013275","DOI":"10.1145\/73833.73863"},{"issue":"No.6","key":"11_CR21","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1109\/TC.1982.1676031","volume":"C-31","author":"D.T. Lee","year":"1982","unstructured":"D.T. Lee, On k-Nearest Neighbor Voronoi Diagrams in the Plane, IEEE Transactions on Computers, Vol. C-31, No. 6, June 1982, pp 478\u2013487","journal-title":"IEEE Transactions on Computers"},{"key":"11_CR22","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF02187867","volume":"2","author":"D. Leven","year":"1987","unstructured":"D. Leven and M. Sharir, Planning a Purely Translational Motion for Convex Objects in Two-Dimensional Space Using Generalized Voronoi Diagrams, Discrete & Computational Geometry, 1987, Vol. 2, pp 9\u201331","journal-title":"Discrete & Computational Geometry"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"H. Noltemeier, Computational Geometry and its Applications, Proceedings Workshop CG '88, Universit\u00e4t W\u00fcrzburg, M\u00e4rz 1988, LNCS 333, Springer Verlag, 1988","DOI":"10.1007\/3-540-50335-8"},{"issue":"No.2","key":"11_CR24","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/130956.130957","volume":"22","author":"J. O'Rourke","year":"1991","unstructured":"J. O'Rourke, Computational Geometry Column 12, SIGACT News, Vol. 22, No. 2, Spring 1991, pp 26\u201329","journal-title":"SIGACT News"},{"key":"11_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry \u2014 An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos, Computational Geometry \u2014 An Introduction, Springer-Verlag, New York, 1985"},{"key":"11_CR26","unstructured":"T. Roos, Voronoi Diagramme, Diplomarbeit, Universit\u00e4t W\u00fcrzburg, 1988"},{"key":"11_CR27","unstructured":"T. Roos, k \u2014 Nearest \u2014 Neighbor Voronoi Diagrams for Sets of Convex Polygons, Line Segments and Points, Proceedings 15th Intern. Workshop on Graph-Theoretic Concepts in Computer Science WG89, LNCS 411, Springer-Verlag, Berlin-Heidelberg-New York"},{"key":"11_CR28","unstructured":"T. Roos, Voronoi Diagrams over Dynamic Scenes (Extended Abstract), Proceedings 2nd Canadian Conference on Computational Geometry, Ottawa, 1990"},{"key":"11_CR29","unstructured":"T. Roos, Voronoi Diagrams over Dynamic Scenes, to appear in Discrete Applied Mathematics, 1991"},{"key":"11_CR30","unstructured":"T. Roos and H. Noltemeier, Dynamic Voronoi Diagrams in Motion Planning, to appear on 15th IFIP Conference on System Modeling and Optimization, Zurich, 1991"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"M.I. Shamos and D. Hoey, Closest \u2014 Point Problems, Proc. 16th Annual Symp. on FOCS, 1975, pp 151\u2013162","DOI":"10.1109\/SFCS.1975.8"},{"key":"11_CR32","series-title":"NATO ASI Series, Vol. F40","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/978-3-642-83539-1_9","volume-title":"Theoretical Foundations of Computer Graphics and CAD","author":"M. Sharir","year":"1988","unstructured":"M. Sharir, Davenport-Schinzel Sequences and their Geometric Applications, pp 253\u2013278, NATO ASI Series, Vol. F40, Theoretical Foundations of Computer Graphics and CAD, R.A. Earnshaw (Ed.), Springer-Verlag Berlin Heidelberg, 1988"},{"key":"11_CR33","unstructured":"K. Sugihara and M. Iri, Construction of the Voronoi Diagram for One Million Generators in Single-Precision Arithmetic, private communications, 1989, to appear in Proc. of IEEE"},{"key":"11_CR34","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/BF02187890","volume":"2","author":"C.K. Yap","year":"1987","unstructured":"C.K. Yap, An O(n log n) Algorithm for theVoronoi Diagram of a Set of Simple Curve Segments, Discrete & Computational Geometry, 1987, Vol. 2, pp 365\u2013393","journal-title":"Discrete & Computational Geometry"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55121-2_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:57:35Z","timestamp":1605646655000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}