{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T11:40:34Z","timestamp":1753357234033,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,9,20]],"date-time":"2018-09-20T00:00:00Z","timestamp":1537401600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["SNF 20GG21-134355","SNF 200021E- 154387"],"award-info":[{"award-number":["SNF 20GG21-134355","SNF 200021E- 154387"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["P2TIP2-168563"],"award-info":[{"award-number":["P2TIP2-168563"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002661","name":"Fonds De La Recherche Scientifique - FNRS","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s10878-018-0347-x","type":"journal-article","created":{"date-parts":[[2018,9,20]],"date-time":"2018-09-20T16:45:21Z","timestamp":1537461921000},"page":"579-600","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5267-4512","authenticated-orcid":false,"given":"Elena","family":"Arseneva","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0144-7384","authenticated-orcid":false,"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,20]]},"reference":[{"key":"347_CR1","unstructured":"Abellanas M, Hurtado F, Icking C, Klein R, Langetepe E, Ma L, Palop B, Sacrist\u00e1n V (2001) The farthest color Voronoi diagram and related problems. In: 17th Eur. workshop on comput. geom. (EWCG), full version: Tech. Rep. 002 2006, Universit\u00e4t Bonn, pp 113\u2013116"},{"key":"347_CR2","doi-asserted-by":"publisher","DOI":"10.1142\/8685","volume-title":"Voronoi diagrams and Delaunay triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer F, Klein R, Lee DT (2013) Voronoi diagrams and Delaunay triangulations. World Scientific, Singapore"},{"key":"347_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational geometry\u2014algorithms and applications","author":"M Berg de","year":"2008","unstructured":"de Berg M, Cheong O, van Kreveld M, Overmars M (2008) Computational geometry\u2014algorithms and applications, 3rd edn. Springer, Berlin","edition":"3"},{"key":"347_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172998","volume-title":"Algorithmic geometry","author":"JD Boissonnat","year":"1998","unstructured":"Boissonnat JD, Yvinec M (1998) Algorithmic geometry. Cambridge University Press, New York"},{"issue":"4","key":"347_CR5","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1007\/s00453-016-0118-y","volume":"76","author":"P Cheilaris","year":"2016","unstructured":"Cheilaris P, Khramtcova E, Langerman S, Papadopoulou E (2016) A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters. Algorithmica 76(4):935\u2013960","journal-title":"Algorithmica"},{"key":"347_CR6","doi-asserted-by":"crossref","unstructured":"Chen DZ, Huang Z, Liu Y, Xu J (2013) On clustering induced Voronoi diagrams. In: 2013 IEEE 54th annual symposium on foundations of computer science (FOCS). IEEE, pp 390\u2013399","DOI":"10.1109\/FOCS.2013.49"},{"issue":"4","key":"347_CR7","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1016\/j.comgeo.2010.11.004","volume":"44","author":"O Cheong","year":"2011","unstructured":"Cheong O, Everett H, Glisse M, Gudmundsson J, Hornus S, Lazard S, Lee M, Na HS (2011) Farthest-polygon Voronoi diagrams. Comput Geom 44(4):234\u2013247","journal-title":"Comput Geom"},{"key":"347_CR8","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K Clarkson","year":"1989","unstructured":"Clarkson K, Shor P (1989) Applications of random sampling in computational geometry II. Discrete Comput Geom 4:387\u2013421","journal-title":"Discrete Comput Geom"},{"issue":"4","key":"347_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0925-7721(93)90009-U","volume":"3","author":"KL Clarkson","year":"1993","unstructured":"Clarkson KL, Mehlhorn K, Seidel R (1993) Four results on randomized incremental constructions. Comput Geom Theory Appl 3(4):185\u2013212","journal-title":"Comput Geom Theory Appl"},{"issue":"3","key":"347_CR10","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1007\/s00453-017-0299-z","volume":"80","author":"M Claverol","year":"2018","unstructured":"Claverol M, Khramtcova E, Papadopoulou E, Saumell M, Seara C (2018) Stabbing circles for sets of segments in the plane. Algorithmica 80(3):849\u2013884","journal-title":"Algorithmica"},{"key":"347_CR11","doi-asserted-by":"crossref","unstructured":"Dehne F, Maheshwari A, Taylor R (2006) A coarse grained parallel algorithm for Hausdorff Voronoi diagrams. In: 35th ICPP, pp 497\u2013504","DOI":"10.1109\/ICPP.2006.5"},{"key":"347_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF02187733","volume":"4","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner H, Guibas L, Sharir M (1989) The upper envelope of piecewise linear functions: algorithms and applications. Discrete Comput Geom 4:311\u2013336","journal-title":"Discrete Comput Geom"},{"key":"347_CR13","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF02189323","volume":"9","author":"DP Huttenlocher","year":"1993","unstructured":"Huttenlocher DP, Kedem K, Sharir M (1993) The upper envelope of Voronoi surfaces and its applications. Discrete Comput Geom 9:267\u2013291","journal-title":"Discrete Comput Geom"},{"key":"347_CR14","doi-asserted-by":"crossref","unstructured":"Klein R (1989) Concrete and abstract Voronoi diagrams, (Lecture Notes in Computer Science), vol 400. Springer","DOI":"10.1007\/3-540-52055-4"},{"issue":"3","key":"347_CR15","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 (1993) Randomized incremental construction of abstract Voronoi diagrams. Comput Geom 3(3):157\u2013184","journal-title":"Comput Geom"},{"key":"347_CR16","unstructured":"Maheshwari A (2018) private communication"},{"issue":"5","key":"347_CR17","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1109\/TCAD.2010.2100550","volume":"30","author":"E Papadopoulou","year":"2011","unstructured":"Papadopoulou E (2011) Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams. IEEE Trans CAD Integr Circuits Syst 30(5):704\u2013717","journal-title":"IEEE Trans CAD Integr Circuits Syst"},{"issue":"2","key":"347_CR18","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s00453-004-1095-0","volume":"40","author":"E Papadopoulou","year":"2004","unstructured":"Papadopoulou E (2004) The Hausdorff Voronoi diagram of point clusters in the plane. Algorithmica 40(2):63\u201382","journal-title":"Algorithmica"},{"issue":"6","key":"347_CR19","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1142\/S0218195904001536","volume":"14","author":"E Papadopoulou","year":"2004","unstructured":"Papadopoulou E, Lee DT (2004) The Hausdorff Voronoi diagram of polygonal objects: a divide and conquer approach. Int J Comput Geom Appl 14(6):421\u2013452","journal-title":"Int J Comput Geom Appl"},{"issue":"1","key":"347_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00009330","volume":"19","author":"R Seidel","year":"1998","unstructured":"Seidel R (1998) The nature and meaning of perturbations in geometric computing. Discrete Comput Geom 19(1):1\u201317","journal-title":"Discrete Comput Geom"},{"key":"347_CR21","unstructured":"Voronoi CAA: Voronoi Critical Area Analysis. IBM VLSI CAD Tool, IBM Microelectronics Division, Burlington, VT, distributed by Cadence. Patents: US6178539, US6317859, US7240306, US7752589, US7752580, US7143371, US20090125852. Distributed by Cadence since 2007"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0347-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0347-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0347-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,10]],"date-time":"2020-11-10T11:01:32Z","timestamp":1605006092000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0347-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,20]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["347"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0347-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,9,20]]},"assertion":[{"value":"20 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}