{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:21:06Z","timestamp":1762273266642,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T00:00:00Z","timestamp":1716249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100014440","name":"Ministerio de Ciencia, Innovaci\u00f3n y Universidades","doi-asserted-by":"publisher","award":["PID2019-104129GB- I00\/ MICIN \/AEI\/ 10.13039\/501100011033","PID2019-104129GB- I00\/ MICIN \/AEI\/ 10.13039\/501100011033","PID2019-104129GB- I00\/ MICIN \/AEI\/ 10.13039\/501100011033"],"award-info":[{"award-number":["PID2019-104129GB- I00\/ MICIN \/AEI\/ 10.13039\/501100011033","PID2019-104129GB- I00\/ MICIN \/AEI\/ 10.13039\/501100011033","PID2019-104129GB- I00\/ MICIN \/AEI\/ 10.13039\/501100011033"]}],"id":[{"id":"10.13039\/100014440","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002809","name":"Generalitat de Catalunya","doi-asserted-by":"publisher","award":["DGR 2017SGR1640","DGR 2017SGR1640"],"award-info":[{"award-number":["DGR 2017SGR1640","DGR 2017SGR1640"]}],"id":[{"id":"10.13039\/501100002809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014440","name":"Ministerio de Ciencia, Innovaci\u00f3n y Universidades","doi-asserted-by":"publisher","award":["PRE2018-085668"],"award-info":[{"award-number":["PRE2018-085668"]}],"id":[{"id":"10.13039\/100014440","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1007\/s10898-024-01386-0","type":"journal-article","created":{"date-parts":[[2024,5,21]],"date-time":"2024-05-21T07:03:35Z","timestamp":1716275015000},"page":"515-549","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The edge labeling of higher order Voronoi diagrams"],"prefix":"10.1007","volume":"90","author":[{"given":"Merc\u00e8","family":"Claverol","sequence":"first","affiliation":[]},{"given":"Andrea","family":"de las Heras Parrilla","sequence":"additional","affiliation":[]},{"given":"Clemens","family":"Huemer","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8998-2121","authenticated-orcid":false,"given":"Alejandra","family":"Mart\u00ednez-Moraian","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,21]]},"reference":[{"key":"1386_CR1","doi-asserted-by":"crossref","unstructured":"Shamos, M.I., Hoey, D.: Closest-point problems. In: 16th Annual Symposium on Foundations of Computer Science (SFCS 1975), pp. 151\u2013162. IEEE (1975)","DOI":"10.1109\/SFCS.1975.8"},{"key":"1386_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470317013","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"A Okabe","year":"2000","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, Chichester (2000)"},{"key":"1386_CR3","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.automatica.2018.12.028","volume":"102","author":"B Jiang","year":"2019","unstructured":"Jiang, B., Sun, Z., Anderson, B.D.O., Lageman, C.: Higher order mobile coverage control with applications to clustering of discrete sets. Automatica 102, 27\u201333 (2019)","journal-title":"Automatica"},{"issue":"6","key":"1386_CR4","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1109\/TMC.2017.2767048","volume":"17","author":"C Qiu","year":"2017","unstructured":"Qiu, C., Shen, H., Chen, K.: An energy-efficient and distributed cooperation mechanism fork-coverage hole detection and healing in WSNs. IEEE Trans. Mob. Comput. 17(6), 1247\u20131259 (2017)","journal-title":"IEEE Trans. Mob. Comput."},{"issue":"6","key":"1386_CR5","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1142\/S021819591100386X","volume":"21","author":"AK Abu-Affash","year":"2011","unstructured":"Abu-Affash, A.K., Carmi, P., Katz, M.J., Morgenstern, G.: Multi cover of a polygon minimizing the sum of areas. Int. J. Comput. Geom. Appl. 21(6), 685\u2013698 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"1386_CR6","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00454-018-0037-6","volume":"61","author":"P O\u2019Neil","year":"2019","unstructured":"O\u2019Neil, P., Wanner, T.: Analyzing the squared distance-to-measure gradient flow system with k-order Voronoi diagrams. Discrete Comput. Geom. 61, 91\u2013119 (2019)","journal-title":"Discrete Comput. Geom."},{"key":"1386_CR7","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s10898-021-01002-5","volume":"80","author":"J Kallrath","year":"2021","unstructured":"Kallrath, J., Ryu, J., Song, C., Lee, M., Kim, D.S.: Near optimal minimal convex hulls of disks. J. Glob. Optim. 80, 551\u2013594 (2021)","journal-title":"J. Glob. Optim."},{"issue":"3","key":"1386_CR8","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams\u2014a survey of a fundamental geometric data structure. ACM Comput. Surv. 23(3), 345\u2013405 (1991)","journal-title":"ACM Comput. Surv."},{"key":"1386_CR9","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, 478\u2013487 (1982)","journal-title":"IEEE Trans. Comput."},{"key":"1386_CR10","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/BFb0036906","volume-title":"Automata, Languages and Programming","author":"F Dehne","year":"1983","unstructured":"Dehne, F.: An $$o(n^4)$$ algorithm to construct all Voronoi diagrams for $$k$$-nearest neighbor searching in the Euclidean plane. In: Diaz, J. (ed.) Automata, Languages and Programming, pp. 160\u2013162. Springer, Berlin (1983)"},{"key":"1386_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Berlin (1987)"},{"key":"1386_CR12","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.comgeo.2017.06.014","volume":"68","author":"H Edelsbrunner","year":"2018","unstructured":"Edelsbrunner, H., Iglesias-Ham, M.: Multiple covers with balls I: inclusion\u2013exclusion. Comput. Geom. Theory Appl. 68, 119\u2013133 (2018)","journal-title":"Comput. Geom. Theory Appl."},{"key":"1386_CR13","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1142\/S0218195911003846","volume":"21","author":"W El Oraiby","year":"2011","unstructured":"El Oraiby, W., Schmit, D., Spehner, J.C.: Centroid triangulations from k-sets. Int. J. Comput. Geom. Appl. 21, 635\u2013659 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"1386_CR14","first-page":"41","volume":"7","author":"RC Lindenbergh","year":"2003","unstructured":"Lindenbergh, R.C.: A Voronoi poset. J. Geom. Graph. 7, 41\u201352 (2003)","journal-title":"J. Geom. Graph."},{"key":"1386_CR15","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s10957-019-01555-2","volume":"183","author":"JE Mart\u00ednez-Legaz","year":"2019","unstructured":"Mart\u00ednez-Legaz, J.E., Roschina, V., Todorov, M.: On the structure of higher order Voronoi cells. J. Optim. Theory Appl. 183, 24\u201349 (2019)","journal-title":"J. Optim. Theory Appl."},{"key":"1386_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.2307\/3213553","volume":"19","author":"RE Miles","year":"1982","unstructured":"Miles, R.E., Maillardet, R.J.: Basic structures of Voronoi and generalized Voronoi polygons. J. Appl. Probab. 19, 97\u2013111 (1982)","journal-title":"J. Appl. Probab."},{"key":"1386_CR17","doi-asserted-by":"crossref","unstructured":"Schmitt, D., Spehner, J.C.: Order-k Voronoi diagrams, k-sections, and k-sets. In: Japanese Conference on Discrete and Computational Geometry 1998, Lecture Notes in Computer Science, pp. 290\u2013304 (1999)","DOI":"10.1007\/978-3-540-46515-7_26"},{"key":"1386_CR18","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00453-013-9809-9","volume":"71","author":"CH Liu","year":"2015","unstructured":"Liu, C.H., Papadopoulou, E., Lee, D.T.: The k-nearest-neighbor Voronoi diagram revisted. Algorithmica 71, 429\u2013449 (2015)","journal-title":"Algorithmica"},{"key":"1386_CR19","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$$\\backslash $$lowercase ($$\\le $$)-levels in three dimensions. SIAM J. Comput. 30, 561\u2013575 (2000)","journal-title":"SIAM J. Comput."},{"key":"1386_CR20","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Edelsbrunner, H.: An improved algorithm for constructing kth-order Voronoi diagrams. In: Proceedings of the First Annual Symposium on Computational Geometry, pp. 228\u2013234 (1985)","DOI":"10.1145\/323233.323263"},{"issue":"2","key":"1386_CR21","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O\u2019Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15(2), 341\u2013363 (1986)","journal-title":"SIAM J. Comput."},{"key":"1386_CR22","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Guibas, L., Saxe, J., Shor, P.: A linear time algorithm for computing the Voronoi diagram of a convex polygon. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 39\u201345 (1987)","DOI":"10.1145\/28395.28400"},{"key":"1386_CR23","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: Applications of random sampling in computational geometry, II. In: Proceedings of the Fourth Annual Symposium on Computational Geometry, pp. 1\u201311 (1988)","DOI":"10.1145\/73393.73394"},{"key":"1386_CR24","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF02187788","volume":"5","author":"F Aurenhammer","year":"1990","unstructured":"Aurenhammer, F.: A new duality result concerning Voronoi diagrams. Discrete Comput. Geom. 5, 243\u2013254 (1990)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"1386_CR25","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF01293483","volume":"13","author":"MJ Agarwal","year":"1995","unstructured":"Agarwal, M.J.: Dynamic half-space range reporting and its applications. Algorithmica 13(4), 325\u2013345 (1995)","journal-title":"Algorithmica"},{"key":"1386_CR26","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":"1386_CR27","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02574692","volume":"6","author":"K Mulmuley","year":"1991","unstructured":"Mulmuley, K.: On levels in arrangements and Voronoi diagrams. Discrete Comput. Geom. 6, 307\u2013338 (1991)","journal-title":"Discrete Comput. Geom."},{"key":"1386_CR28","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., De\u00a0Berg, M., Matou\u0161ek, J., Schwarzkopf, O.: Constructing levels in arrangements and higher order Voronoi diagrams. In: Proceedings of the Tenth Annual Symposium on Computational Geometry, pp. 67\u201375 (1994)","DOI":"10.1145\/177424.177521"},{"key":"1386_CR29","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, pp. 390\u2013399 (1999)","DOI":"10.1145\/304893.304993"},{"key":"1386_CR30","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, 329\u2013356 (1993)","journal-title":"Algorithmica"},{"key":"1386_CR31","doi-asserted-by":"crossref","unstructured":"Aurenhammer, F., Schwarzkopf, O.: A simple on-line randomized incremental algorithm for computing higher order Voronoi diagrams. In: Proceedings of the Seventh Annual Symposium on Computational Geometry, pp. 142\u2013151 (1991)","DOI":"10.1145\/109648.109664"},{"key":"1386_CR32","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1112\/blms\/16.3.241","volume":"16","author":"GA Jones","year":"1984","unstructured":"Jones, G.A.: Geometric and asymptotic properties of Brillouin zones in lattices. Bull. Lond. Math. Soc. 16, 241\u2013263 (1984)","journal-title":"Bull. Lond. Math. Soc."},{"key":"1386_CR33","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1007\/PL00020959","volume":"212","author":"JJP Veerman","year":"2000","unstructured":"Veerman, J.J.P., Peixoto, M.M., Rochal, A.C., Sutherland, S.: On Brillouin zones. Commun. Math. Phys. 212, 725\u2013744 (2000)","journal-title":"Commun. Math. Phys."},{"key":"1386_CR34","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF01896768","volume":"27","author":"GF T\u00f3th","year":"1976","unstructured":"T\u00f3th, G.F.: Multiple packing and covering of the plane with circles. Acta Math. Acad. Sci. Hung. 27, 135\u2013140 (1976)","journal-title":"Acta Math. Acad. Sci. Hung."},{"key":"1386_CR35","first-page":"1","volume":"27","author":"F Jaeger","year":"1985","unstructured":"Jaeger, F.: A survey on the cycle double cover conjecture. Ann. Discrete Math. 27, 1\u201312 (1985)","journal-title":"Ann. Discrete Math."},{"key":"1386_CR36","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/978-94-009-0517-7_4","volume-title":"Circles and Rays","author":"JA Bondy","year":"1990","unstructured":"Bondy, J.A.: Small cycle double covers of graphs. In: Hahn, G., Sabidussi, G., Woodrow, R.E. (eds.) Circles and Rays, pp. 21\u201340. Springer, Dordrecht (1990)"},{"key":"1386_CR37","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF01303519","volume":"13","author":"K Seyffarth","year":"1993","unstructured":"Seyffarth, K.: Small cycle double covers of 4-connected planar graphs. Combinatorica 13, 477\u2013482 (1993)","journal-title":"Combinatorica"},{"key":"1386_CR38","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0012-365X(92)90610-R","volume":"101","author":"K Seyffarth","year":"1992","unstructured":"Seyffarth, K.: Haj\u00f3s conjecture and small cycle double covers of planar graphs. Discrete Math. 101, 291\u2013306 (1992)","journal-title":"Discrete Math."},{"key":"1386_CR39","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02187681","volume":"1","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Seidel, R.: Voronoi diagrams and arrangements. Discrete Comput. Geom. 1, 25\u201344 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"1386_CR40","unstructured":"de\u00a0las Heras\u00a0Parrilla, A.: Properties for Voronoi Diagrams of Arbitrary Order in the Sphere. Master Thesis. Universitat Polit\u00e8cnica de Catalunya (2021). https:\/\/upcommons.upc.edu\/handle\/2117\/354664"},{"issue":"8","key":"1386_CR41","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."},{"key":"1386_CR42","doi-asserted-by":"publisher","first-page":"2317","DOI":"10.1007\/s00453-018-00536-7","volume":"81","author":"C Bohler","year":"2019","unstructured":"Bohler, C., Klein, R., Liu, C.H.: An efficient randomized algorithm for higher order abstract Voronoi diagrams. Algorithmica 81, 2317\u20132345 (2019)","journal-title":"Algorithmica"},{"key":"1386_CR43","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/B978-0-7204-2262-7.50018-1","volume-title":"A Survey of Combinatorial Theory","author":"P Erd\u0151s","year":"1973","unstructured":"Erd\u0151s, P., Lov\u00e1sz, L., Simmons, A., Straus, E.G.: Dissection graphs of planar point sets. In: Srivastava, J.N. (ed.) A Survey of Combinatorial Theory, pp. 139\u2013149. Elsevier, Amsterdam (1973)"},{"key":"1386_CR44","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/PL00009354","volume":"19","author":"T Dey","year":"1989","unstructured":"Dey, T.: Improved bounds for planar k-sets and related problems. Discrete Comput. Geom. 19, 373\u2013382 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"1386_CR45","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(93)90115-5","volume":"43","author":"T Roos","year":"1993","unstructured":"Roos, T.: Voronoi diagrams over dynamic scenes. Discrete Appl. Math. 43, 243\u2013259 (1993)","journal-title":"Discrete Appl. Math."},{"key":"1386_CR46","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/282918.282923","volume":"4","author":"L Guibas","year":"1985","unstructured":"Guibas, L., Stolfi, J., Spehner, J.C.: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph 4, 74\u2013123 (1985)","journal-title":"ACM Trans. Graph"},{"key":"1386_CR47","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0097-3165(86)90122-6","volume":"41","author":"N Alon","year":"1986","unstructured":"Alon, N., Gy\u0151ri, E.: The number of small semi-spaces of a finite set of points in the plane. J. Combin. Theory Ser. A. 41, 154\u2013157 (1986)","journal-title":"J. Combin. Theory Ser. A."},{"issue":"1453","key":"1386_CR48","first-page":"1","volume":"10","author":"A Dobrin","year":"2005","unstructured":"Dobrin, A.: A review of properties and variations of Voronoi diagrams. Whitman Coll. 10(1453), 1\u201343 (2005)","journal-title":"Whitman Coll."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01386-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01386-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01386-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,21]],"date-time":"2024-09-21T05:03:08Z","timestamp":1726894988000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01386-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,21]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["1386"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01386-0","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2024,5,21]]},"assertion":[{"value":"8 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}