{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:29Z","timestamp":1740109289445,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T00:00:00Z","timestamp":1545091200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["Kl 655\/19"],"award-info":[{"award-number":["Kl 655\/19"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-018-00536-7","type":"journal-article","created":{"date-parts":[[2018,12,18]],"date-time":"2018-12-18T05:18:07Z","timestamp":1545110287000},"page":"2317-2345","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams"],"prefix":"10.1007","volume":"81","author":[{"given":"Cecilia","family":"Bohler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9683-5982","authenticated-orcid":false,"given":"Chih-Hung","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,18]]},"reference":[{"issue":"3","key":"536_CR1","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1137\/S0097539795281840","volume":"27","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., de Berg, M., Matousek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. SIAM J. Comput. 27(3), 654\u2013667 (1998)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"536_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. Int. J. Comput. Geom. Appl. 2(4), 363\u2013381 (1992)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"8","key":"536_CR3","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/j.comgeo.2015.04.008","volume":"48","author":"C Bohler","year":"2015","unstructured":"Bohler, C., Cheilaris, P., Klein, R., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: On the complexity of higher order abstract Voronoi diagrams. Comput. Geom. 48(8), 539\u2013551 (2015)","journal-title":"Comput. Geom."},{"issue":"4","key":"536_CR4","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1142\/S0218195914600115","volume":"24","author":"C Bohler","year":"2014","unstructured":"Bohler, C., Klein, R.: Abstract Voronoi diagrams with disconnected regions. Int. J. Comput. Geom. Appl. 24(4), 347\u2013372 (2014)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"536_CR5","unstructured":"Bohler, C., Klein, R., Liu, C.-H.: An efficient randomized algorithm for higher-order abstract Voronoi diagrams. In: Proceeding of the 32nd International Symposium on Computational Geometry (SoCG 2016), pp. 21:1\u201321:15 (2016)"},{"key":"536_CR6","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.comgeo.2016.08.004","volume":"59","author":"C Bohler","year":"2016","unstructured":"Bohler, C., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams. Comput. Geom. 59, 26\u201338 (2016)","journal-title":"Comput. Geom."},{"issue":"4","key":"536_CR7","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 9(4), 329\u2013356 (1993)","journal-title":"Algorithmica"},{"issue":"2","key":"536_CR8","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"TM Chan","year":"2000","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of (\n                    \n                      \n                    \n                    $$\\le k$$\n                    \n                      \n                        \n                          \u2264\n                          k\n                        \n                      \n                    \n                  )-levels in three dimensions. SIAM J. Comput. 30(2), 561\u2013575 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"536_CR9","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1007\/s00454-016-9784-4","volume":"56","author":"TM Chan","year":"2016","unstructured":"Chan, T.M., Tsakalidis, K.: Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discrete Comput. Geom. 56(4), 866\u2013881 (2016)","journal-title":"Discrete Comput. Geom."},{"key":"536_CR10","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/BF02574703","volume":"6","author":"B Chazelle","year":"1991","unstructured":"Chazelle, B.: Triangulating a simple polygon in linear time. Discrete Comput. Geom. 6, 485\u2013524 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"11","key":"536_CR11","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 \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -th-order Voronoi diagrams. IEEE Trans. Comput. 36(11), 1349\u20131354 (1987)","journal-title":"IEEE Trans. Comput."},{"issue":"6","key":"536_CR12","doi-asserted-by":"publisher","first-page":"1286","DOI":"10.1137\/0222077","volume":"22","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M., Snoeyink, J.: Computing a face in an arrangement of line segments and related problems. SIAM J. Comput. 22(6), 1286\u20131302 (1993)","journal-title":"SIAM J. Comput."},{"key":"536_CR13","doi-asserted-by":"crossref","unstructured":"Chew, L.P., Scot Drysdale, R.L.: Voronoi diagrams based on convex distance functions. In: Proceedings of the First Annual Symposium on Computational Geometry, (SoCG 1985), pp. 235\u2013244 (1985)","DOI":"10.1145\/323233.323264"},{"key":"536_CR14","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"KL Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195\u2013222 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"536_CR15","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Application of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"536_CR16","doi-asserted-by":"crossref","unstructured":"Gemsa, A., Lee, D.T., Liu, C.-H., Wagner, D.: Higher order city Voronoi diagrams. In: Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 59\u201370 (2012)","DOI":"10.1007\/978-3-642-31155-0_6"},{"key":"536_CR17","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"536_CR18","doi-asserted-by":"crossref","unstructured":"Klein, R.: Voronoi diagrams in the Moscow metric (extended abstract). In: Proceedings of the 14th International Workshop of Graph-Theoretic Concepts in Computer Science (WG88), pp. 434\u2013441 (1988)","DOI":"10.1007\/3-540-50728-0_61"},{"key":"536_CR19","series-title":"Volume 400 of Lecture Notes in Computer Science","doi-asserted-by":"publisher","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. Volume 400 of Lecture Notes in Computer Science. Springer, Berlin (1989)"},{"issue":"9","key":"536_CR20","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. Comput. Geom. 42(9), 885\u2013902 (2009)","journal-title":"Comput. Geom."},{"key":"536_CR21","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. Comput. Geom. 3, 157\u2013184 (1993)","journal-title":"Comput. Geom."},{"issue":"6","key":"536_CR22","first-page":"478","volume":"31","author":"DT Lee","year":"1982","unstructured":"Lee, D.T.: On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput. 31(6), 478\u2013487 (1982)","journal-title":"IEEE Trans. Comput."},{"key":"536_CR23","doi-asserted-by":"crossref","unstructured":"Liu, C.-H., Lee, D.T.: Higher-order geodesic Voronoi diagrams in a polygonal domain with holes. In: Proceedings of the Twenty-Fourth Annual Symposium on Discrete Algorithms (SODA), pp. 1633\u20131645 (2013)","DOI":"10.1137\/1.9781611973105.117"},{"issue":"6","key":"536_CR24","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1142\/S0218195901000663","volume":"11","author":"K Mehlhorn","year":"2001","unstructured":"Mehlhorn, K., Meiser, S., Rasch, R.: Furthest site abstract Voronoi diagrams. Int. J. Comput. Geom. Appl. 11(6), 583\u2013616 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"536_CR25","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1994)"},{"issue":"2","key":"536_CR26","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00453-004-1095-0","volume":"40","author":"E Papadopoulou","year":"2004","unstructured":"Papadopoulou, E.: The Hausdorff Voronoi diagram of point clusters in the plane. Algorithmica 40(2), 63\u201382 (2004)","journal-title":"Algorithmica"},{"issue":"1","key":"536_CR27","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s00453-014-9950-0","volume":"74","author":"E Papadopoulou","year":"2016","unstructured":"Papadopoulou, E., Zavershynskyi, M.: On higher order Voronoi diagrams of line segments. Algorithmica 74(1), 415\u2013439 (2016)","journal-title":"Algorithmica"},{"key":"536_CR28","doi-asserted-by":"crossref","unstructured":"Ramos, E.A.: On range reporting, ray shooting and k-level construction. In: Proceedings of the Fifteenth Annual Symposium on Computational Geometry (SoCG), pp. 390\u2013399 (1999)","DOI":"10.1145\/304893.304993"},{"issue":"1","key":"536_CR29","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1137\/0217010","volume":"17","author":"RE Tarjan","year":"1988","unstructured":"Tarjan, R.E., Van Wyk, C.J.: An \n                    \n                      \n                    \n                    $$O(n \\log \\log n)$$\n                    \n                      \n                        \n                          O\n                          (\n                          n\n                          log\n                          log\n                          n\n                          )\n                        \n                      \n                    \n                  -time algorithm for triangulating a simple polygon. SIAM J. Comput. 17(1), 143\u2013178 (1988)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00536-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-00536-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00536-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T19:20:14Z","timestamp":1576610414000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-00536-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,18]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["536"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-00536-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,12,18]]},"assertion":[{"value":"19 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}