{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:27:27Z","timestamp":1760441247647,"version":"3.40.5"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130743"},{"type":"electronic","value":"9783319130750"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_3","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"27-37","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams"],"prefix":"10.1007","author":[{"given":"Cecilia","family":"Bohler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chih-Hung","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maksym","family":"Zavershynskyi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., de Berg, M., Matou\u0161ek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM Journal on Computing\u00a027(3), 654\u2013667 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"3_CR2","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1142\/S0218195992000214","volume":"2","author":"F. Aurenhammer","year":"1992","unstructured":"Aurenhammer, F., Schwarzkopf, O.: A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. International Journal of Computational Geometry and Applications\u00a02(4), 363\u2013381 (1992)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-642-39206-1_18","volume-title":"Automata, Languages, and Programming","author":"C. Bohler","year":"2013","unstructured":"Bohler, C., Cheilaris, P., Klein, R., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: On the complexity of higher order abstract Voronoi diagrams. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 208\u2013219. Springer, Heidelberg (2013)"},{"key":"3_CR4","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF01228508","volume":"9","author":"J.D. Boissonnat","year":"1993","unstructured":"Boissonnat, J.D., Devillers, O., Teillaud, M.: A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis. Algorithmica\u00a09, 329\u2013356 (1993)","journal-title":"Algorithmica"},{"issue":"2","key":"3_CR5","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"T.M. Chan","year":"1998","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of (\u2264\u2009k)-levels in three dimensions. SIAM Journal on Computing\u00a030(2), 561\u2013572 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"11","key":"3_CR6","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1109\/TC.1987.5009474","volume":"36","author":"B. Chazelle","year":"1987","unstructured":"Chazelle, B., Edelsbrunner, H.: An improved algorithm for constructing kth-order Voronoi Diagram. IEEE Transactions on Computers\u00a036(11), 1349\u20131454 (1987)","journal-title":"IEEE Transactions on Computers"},{"issue":"1","key":"3_CR7","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K.L. Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete and Computational Geometry\u00a02(1), 195\u2013222 (1987)","journal-title":"Discrete and Computational Geometry"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-31155-0_6","volume-title":"Algorithm Theory \u2013 SWAT 2012","author":"A. Gemsa","year":"2012","unstructured":"Gemsa, A., Lee, D.T., Liu, C.-H., Wagner, D.: Higher order city Voronoi diagrams. In: Fomin, F.V., Kaski, P. (eds.) SWAT 2012. LNCS, vol.\u00a07357, pp. 59\u201370. Springer, Heidelberg (2012)"},{"issue":"4","key":"3_CR9","doi-asserted-by":"publisher","first-page":"1341","DOI":"10.1137\/S0097539799362627","volume":"30","author":"S. Har-Peled","year":"2000","unstructured":"Har-Peled, S.: Taking a walk in a planar arrangment. SIAM Journal on Computing\u00a030(4), 1341\u20131367 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-52055-4","volume-title":"Concrete and Abstract Voronoi Diagrams","author":"R. Klein","year":"1989","unstructured":"Klein, R.: Concrete and Abstract Voronoi Diagrams. LNCS, vol.\u00a0400. Springer, Heidelberg (1989)"},{"issue":"9","key":"3_CR11","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1016\/j.comgeo.2009.03.002","volume":"42","author":"R. Klein","year":"2009","unstructured":"Klein, R., Langetepe, E., Nilforoushan, Z.: Abstract Voronoi Diagrams Revisited. Computational Geometry: Theory and Applications\u00a042(9), 885\u2013902 (2009)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"1","key":"3_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0925-7721(93)90033-3","volume":"3","author":"R. Klein","year":"1993","unstructured":"Klein, R., Mehlhorn, K., Meiser, S.: Randomized Incremental Construction of Abstract Voronoi Diagrams. Computational Geometry: Theory and Applications\u00a03(1), 157\u2013184 (1993)","journal-title":"Computational Geometry: Theory and Applications"},{"issue":"1","key":"3_CR13","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF02574686","volume":"6","author":"K. Mehlhorn","year":"1991","unstructured":"Mehlhorn, K., Meiser, S., \u00d3\u2019D\u00fanlaing, C.: On the Construction of Abstract Voronoi Diagrams. Discrete and Computational Geometry\u00a06(1), 211\u2013224 (1991)","journal-title":"Discrete and Computational Geometry"},{"issue":"6","key":"3_CR14","first-page":"478","volume":"31","author":"D.T. Lee","year":"1982","unstructured":"Lee, D.T.: On k Nearest Neighbor Voronoi Diagrams in the Plane. IEEE Trans. Computers\u00a031(6), 478\u2013487 (1982)","journal-title":"IEEE Trans. Computers"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Liu, C.-H., Lee, D.T.: Higher-order geodesic Voronoi diagrams in a polygonal domain with holes. In: 2013 ACM-SIAM Symposium on Discrete Algorithms, pp. 1633\u20131645 (2013)","DOI":"10.1137\/1.9781611973105.117"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-642-23719-5_7","volume-title":"Algorithms \u2013 ESA 2011","author":"C.-H. Liu","year":"2011","unstructured":"Liu, C.-H., Papadopoulou, E., Lee, D.T.: An output-sensitive approach for the L 1\/L \u2009\u221e\u2009 k-Nearest-Neighbor Voronoi diagram. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol.\u00a06942, pp. 70\u201381. Springer, Heidelberg (2011)"},{"key":"3_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-35261-4_21","volume-title":"Algorithms and Computation","author":"E. Papadopoulou","year":"2012","unstructured":"Papadopoulou, E., Zavershynskyi, M.: On Higher Order Voronoi Diagrams of Line Segments. In: Chao, K.-M., Hsu, T.-s., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol.\u00a07676, pp. 177\u2013186. Springer, Heidelberg (2012)"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Ramos, E.: On range reporting, ray shooting, and k-level construction. In: 15th ACM Symposium on Computational Geometry, pp. 390\u2013399 (1999)","DOI":"10.1145\/304893.304993"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Zavershynskyi, M., Papadopoulou, E.: A sweepline algorithm for higher order Voronoi diagrams. In: Proc. 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD). IEEE-CS (2013)","DOI":"10.1109\/ISVD.2013.17"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:11:27Z","timestamp":1747159887000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}