{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:46Z","timestamp":1740109246259,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,1,28]],"date-time":"2016-01-28T00:00:00Z","timestamp":1453939200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["20GG21-134355"],"award-info":[{"award-number":["20GG21-134355"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1007\/s00453-016-0118-y","type":"journal-article","created":{"date-parts":[[2016,1,28]],"date-time":"2016-01-28T15:38:01Z","timestamp":1453995481000},"page":"935-960","update-policy":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A Randomized Incremental Algorithm for the Hausdorff Voronoi Diagram of Non-crossing Clusters"],"prefix":"10.1007","volume":"76","author":[{"given":"Panagiotis","family":"Cheilaris","sequence":"first","affiliation":[]},{"given":"Elena","family":"Khramtcova","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]},{"given":"Evanthia","family":"Papadopoulou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,28]]},"reference":[{"issue":"3","key":"118_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/PL00009296","volume":"17","author":"M Abellanas","year":"1997","unstructured":"Abellanas, M., Hernandez, G., Klein, R., Neumann-Lara, V., Urrutia, J.: A combinatorial property of convex sets. Discrete Comput. Geom. 17(3), 307\u2013318 (1997)","journal-title":"Discrete Comput. Geom."},{"key":"118_CR2","unstructured":"Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacrist\u00e1n, V.: The farthest color Voronoi diagram and related problems. In: Proceedings of the 17th European Workshop on Computional Geometry (EWCG), pp. 113\u2013116 (2001)"},{"key":"118_CR3","doi-asserted-by":"crossref","unstructured":"Arge, L., Brodal, G.S., Georgiadis, L.: Improved dynamic planar point location. In: Proceedings of the 47th Symposium on Foundations of Computer Science (FOCS), pp. 305\u2013314 (2006)","DOI":"10.1109\/FOCS.2006.40"},{"key":"118_CR4","doi-asserted-by":"crossref","unstructured":"Aronov, B., Bose, P., Demaine, E.D., Gudmundsson, J., Iacono, J., Langerman, S., Smid, M.: Data structures for halfplane proximity queries and incremental Voronoi diagrams. In: Proceedings of the 7th Latin American Symposium on Theoretical Informatics (LATIN), pp. 80\u201392. Springer, Berlin, Heidelberg (2006)","DOI":"10.1007\/11682462_12"},{"key":"118_CR5","doi-asserted-by":"crossref","DOI":"10.1142\/8685","volume-title":"Voronoi Diagrams and Delaunay Triangulations","author":"F Aurenhammer","year":"2013","unstructured":"Aurenhammer, F., Klein, R., Lee, D.T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Company, Singapore (2013)"},{"issue":"3","key":"118_CR6","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1006\/jagm.1994.1040","volume":"17","author":"H Baumgarten","year":"1994","unstructured":"Baumgarten, H., Jung, H., Mehlhorn, K.: Dynamic point location in general subdivisions. J. Algorithms 17(3), 342\u2013380 (1994)","journal-title":"J. Algorithms"},{"key":"118_CR7","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/978-3-540-33259-6_2","volume-title":"Effective Computational Geometry for Curves and Surfaces","author":"JD Boissonnat","year":"2006","unstructured":"Boissonnat, J.D., Wormser, C., Yvinec, M.: Curved Voronoi diagrams. In: Boissonnat, J.D., Teillaud, M. (eds.) Effective Computational Geometry for Curves and Surfaces, pp. 67\u2013116. Springer, Berlin (2006)"},{"issue":"4","key":"118_CR8","doi-asserted-by":"crossref","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, H.S.: Farthest-polygon Voronoi diagrams. Comput. Geom. 44(4), 234\u2013247 (2011)","journal-title":"Comput. Geom."},{"issue":"1","key":"118_CR9","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K Clarkson","year":"1989","unstructured":"Clarkson, K., Shor, P.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4(1), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"118_CR10","doi-asserted-by":"crossref","unstructured":"Dehne, F., Maheshwari, A., Taylor, R.: A coarse grained parallel algorithm for Hausdorff Voronoi diagrams. In: Proceedings of the 35th International Conference on Parallel Processing (ICPP), pp. 497\u2013504 (2006)","DOI":"10.1109\/ICPP.2006.5"},{"issue":"2","key":"118_CR11","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1142\/S0129054102001035","volume":"13","author":"O Devillers","year":"2002","unstructured":"Devillers, O.: The Delaunay hierarchy. Int. J. Found. Comput. Sci. 13(2), 163\u2013180 (2002)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"118_CR12","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0196-6774(85)90039-2","volume":"6","author":"H Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H.: Computing the extreme distances between two convex polygons. J. Algorithms 6(2), 213\u2013224 (1985)","journal-title":"J. Algorithms"},{"issue":"1","key":"118_CR13","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1007\/BF02187733","volume":"4","author":"H Edelsbrunner","year":"1989","unstructured":"Edelsbrunner, H., Guibas, L.J., Sharir, M.: The upper envelope of piecewise linear functions: algorithms and applications. Discrete Comput. Geom. 4(1), 311\u2013336 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"118_CR14","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1007\/BF02189323","volume":"9","author":"DP Huttenlocher","year":"1993","unstructured":"Huttenlocher, D.P., Kedem, K., Sharir, M.: The upper envelope of Voronoi surfaces and its applications. Discrete Comput. Geom. 9(1), 267\u2013291 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"118_CR15","doi-asserted-by":"crossref","unstructured":"Karavelas, M.I., Yvinec, M.: The voronoi diagram of planar convex objects. In: Di Battista, G., Zwick, U. (eds.) Algorithms\u2014ESA 2003. Lecture Notes in Computer Science, vol. 2832, pp. 337\u2013348. Springer, Berlin, Heidelberg (2003)","DOI":"10.1007\/978-3-540-39658-1_32"},{"key":"118_CR16","unstructured":"Khramtcova, E., Papadopoulou, E.: A simple RIC for the Hausdorff Voronoi diagram of non-crossing clusters. In: Abstracts of the 30th European Workshop on Computational Geometry (EuroCG) (2014)"},{"key":"118_CR17","doi-asserted-by":"crossref","unstructured":"Klein, R.: Concrete and abstract Voronoi diagrams, Lecture Notes in Computer Science, vol. 400. Springer (1989)","DOI":"10.1007\/3-540-52055-4"},{"issue":"3","key":"118_CR18","doi-asserted-by":"crossref","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(3), 157\u2013184 (1993)","journal-title":"Comput. Geom."},{"issue":"1","key":"118_CR19","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF02716580","volume":"15","author":"M McAllister","year":"1996","unstructured":"McAllister, M., Kirkpatrick, D.G., Snoeyink, J.: A compact piecewise-linear Voronoi diagram for convex sites in the plane. Discrete Comput. Geom. 15(1), 73\u2013105 (1996)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"118_CR20","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1137\/0210023","volume":"10","author":"N Megiddo","year":"1981","unstructured":"Megiddo, N., Tamir, A., Zemel, E., Chandrasekaran, R.: An $${O}(n\\log ^2n)$$ O ( n log 2 n ) algorithm for the $$k$$ k th longest path in a tree with applications to location problems. SIAM J. Comput. 10(2), 328\u2013337 (1981)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"118_CR21","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1109\/43.920683","volume":"20","author":"E Papadopoulou","year":"2001","unstructured":"Papadopoulou, E.: Critical area computation for missing material defects in VLSI circuits. IEEE Trans. Comput. Aided Des. 20(5), 583\u2013597 (2001)","journal-title":"IEEE Trans. Comput. Aided Des."},{"issue":"2","key":"118_CR22","doi-asserted-by":"crossref","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":"5","key":"118_CR23","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1109\/TCAD.2010.2100550","volume":"30","author":"E Papadopoulou","year":"2011","unstructured":"Papadopoulou, E.: Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams. IEEE Trans. Comput. Aided Des. 30(5), 704\u2013716 (2011)","journal-title":"IEEE Trans. Comput. Aided Des."},{"issue":"6","key":"118_CR24","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1142\/S0218195904001536","volume":"14","author":"E Papadopoulou","year":"2004","unstructured":"Papadopoulou, E., Lee, D.T.: The Hausdorff Voronoi diagram of polygonal objects: a divide and conquer approach. Int. J. Comput. Geom. Appl. 14(6), 421\u2013452 (2004)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"2","key":"118_CR25","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1142\/S0218195915500089","volume":"25","author":"E Papadopoulou","year":"2015","unstructured":"Papadopoulou, E., Xu, J.: The $$L_\\infty $$ L \u221e Hausdorff Voronoi diagram revisited. Int. J. Comput. Geom. Appl. 25(2), 123\u2013141 (2015)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"6","key":"118_CR26","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W Pugh","year":"1990","unstructured":"Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. ACM Commun 33(6), 668\u2013676 (1990)","journal-title":"ACM Commun"},{"issue":"1","key":"118_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/PL00009330","volume":"19","author":"R Seidel","year":"1998","unstructured":"Seidel, R.: The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom. 19(1), 1\u201317 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"118_CR28","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1017\/S0963548302005527","volume":"12","author":"M Sharir","year":"2003","unstructured":"Sharir, M.: The Clarkson\u2013Shor technique revisited and extended. Comb. Probab. Comput. 12(2), 191\u2013201 (2003)","journal-title":"Comb. Probab. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0118-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/article\/10.1007\/s00453-016-0118-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0118-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0118-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:23Z","timestamp":1559072843000},"score":1,"resource":{"primary":{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/10.1007\/s00453-016-0118-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,28]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["118"],"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/s00453-016-0118-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,1,28]]}}}