{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:22:27Z","timestamp":1772119347231,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:00:00Z","timestamp":1749168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T00:00:00Z","timestamp":1749168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021E-154387"],"award-info":[{"award-number":["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":["200021E-201356"],"award-info":[{"award-number":["200021E-201356"]}],"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":["200021E-201356"],"award-info":[{"award-number":["200021E-201356"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3","doi-asserted-by":"publisher","award":["PID2019-104129GB-I00\/ MICIU\/ AEI\/ 10.13039\/501100011033"],"award-info":[{"award-number":["PID2019-104129GB-I00\/ MICIU\/ AEI\/ 10.13039\/501100011033"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100030993","name":"Universit\u00e0 della Svizzera italiana","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100030993","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The farthest-color Voronoi diagram (FCVD) is defined on a set of\n                    <jats:italic>n<\/jats:italic>\n                    points in the plane, where each point is labeled with one of\n                    <jats:italic>m<\/jats:italic>\n                    colors. The colored points constitute a family\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {P}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>P<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    of\n                    <jats:italic>m<\/jats:italic>\n                    clusters (sets) of points in the plane whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, data imprecision, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n\\alpha (m)+\\textit{str}(\\mathcal {P}))$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mi>\u03b1<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>str<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>P<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\textit{str}(\\mathcal {P})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>str<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>P<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a parameter reflecting the number of\n                    <jats:italic>straddles<\/jats:italic>\n                    between pairs of clusters, which is\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(m(n-m))$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>-<\/mml:mo>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . The bound reduces to\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n+ \\textit{str}(\\mathcal {P}))$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>str<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>P<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    if the clusters are pairwise\n                    <jats:italic>non-crossing<\/jats:italic>\n                    . We also present a lower bound, establishing that the complexity of the FCVD can be\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\Omega (n+m^2)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03a9<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>m<\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O((n+\\textit{str}(\\mathcal {P}))\\log ^3 n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mo>+<\/mml:mo>\n                              <mml:mi>str<\/mml:mi>\n                              <mml:mrow>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mi>P<\/mml:mi>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:msup>\n                              <mml:mo>log<\/mml:mo>\n                              <mml:mn>3<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -time, and in certain special cases in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(n\\log n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time.\n                  <\/jats:p>","DOI":"10.1007\/s00453-025-01311-1","type":"journal-article","created":{"date-parts":[[2025,6,6]],"date-time":"2025-06-06T01:14:12Z","timestamp":1749172452000},"page":"1393-1419","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Farthest Color Voronoi Diagram in the Plane"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8256-8107","authenticated-orcid":false,"given":"Ioannis","family":"Mantas","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0202-4543","authenticated-orcid":false,"given":"Rodrigo I.","family":"Silveira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4207-198X","authenticated-orcid":false,"given":"Zeyu","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,6]]},"reference":[{"key":"1311_CR1","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 Computational Geometry (EuroCG 2001). pp. 113\u2013116. (2001)"},{"key":"1311_CR2","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.tcs.2022.07.016","volume":"930","author":"A Acharyya","year":"2022","unstructured":"Acharyya, A., Jallu, R.K., Keikha, V., L\u00f6ffler, M., Saumell, M.: Minimum color spanning circle of imprecise points. Theoret. Comput. Sci. 930, 116\u2013127 (2022)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1311_CR3","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0925-7721(96)00004-1","volume":"8","author":"B Aronov","year":"1997","unstructured":"Aronov, B., Sharir, M.: The common exterior of convex polygons in the plane. Comput. Geom. 8(3), 139\u2013149 (1997)","journal-title":"Comput. Geom."},{"issue":"2","key":"1311_CR4","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/s10878-018-0347-x","volume":"37","author":"E Arseneva","year":"2019","unstructured":"Arseneva, E., Papadopoulou, E.: Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended. J. Comb. Optim. 37(2), 579\u2013600 (2019). https:\/\/doi.org\/10.1007\/s10878-018-0347-x","journal-title":"J. Comb. Optim."},{"key":"1311_CR5","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.ipl.2006.07.008","volume":"100","author":"F Aurenhammer","year":"2006","unstructured":"Aurenhammer, F., Drysdale, R., Krasser, H.: Farthest line segment Voronoi diagrams. Inform. Process. Lett. 100, 220\u2013225 (2006)","journal-title":"Inform. Process. Lett."},{"key":"1311_CR6","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, D.T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, UK (2013). https:\/\/doi.org\/10.1142\/8685"},{"issue":"3","key":"1311_CR7","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1587\/transinf.E95.D.731","volume":"95","author":"SW Bae","year":"2012","unstructured":"Bae, S.W.: On linear-sized farthest-color Voronoi diagrams. IEICE Trans. Inf. Syst. 95(3), 731\u2013736 (2012). https:\/\/doi.org\/10.1587\/transinf.E95.D.731","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"16","key":"1311_CR8","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1016\/j.ipl.2010.05.014","volume":"110","author":"SW Bae","year":"2010","unstructured":"Bae, S.W., Lee, C., Choi, S.: On exact solutions to the Euclidean bottleneck Steiner tree problem. Inf. Process. Lett. 110(16), 672\u2013678 (2010). https:\/\/doi.org\/10.1016\/j.ipl.2010.05.014","journal-title":"Inf. Process. Lett."},{"issue":"8","key":"1311_CR9","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). https:\/\/doi.org\/10.1016\/j.comgeo.2015.04.008","journal-title":"Comput. Geom."},{"issue":"4","key":"1311_CR10","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/s00454-004-1152-0","volume":"33","author":"D Bremner","year":"2005","unstructured":"Bremner, D., Demaine, E., Erickson, J., Iacono, J., Langerman, S., Morin, P., Toussaint, G.: Output-sensitive algorithms for computing nearest-neighbour decision boundaries. Discrete Comput. Geometry 33(4), 593\u2013604 (2005). https:\/\/doi.org\/10.1007\/s00454-004-1152-0","journal-title":"Discrete Comput. Geometry"},{"issue":"1","key":"1311_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s10707-019-00373-y","volume":"24","author":"L Chen","year":"2020","unstructured":"Chen, L., Shang, S., Yang, C., Li, J.: Spatial keyword search: a survey. GeoInformatica 24(1), 85\u2013106 (2020). https:\/\/doi.org\/10.1007\/s10707-019-00373-y","journal-title":"GeoInformatica"},{"issue":"3","key":"1311_CR12","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.: Stabbing circles for sets of segments in the plane. Algorithmica 80(3), 849\u2013884 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0299-z","journal-title":"Algorithmica"},{"key":"1311_CR13","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 Compt. Geometry 1, 25\u201344 (1986)","journal-title":"Discrete Compt. Geometry"},{"issue":"1","key":"1311_CR14","doi-asserted-by":"publisher","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 Compt. Geometry 4(1), 311\u2013336 (1989). https:\/\/doi.org\/10.1007\/BF02187733","journal-title":"Discrete Compt. Geometry"},{"issue":"3","key":"1311_CR15","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/BF01934440","volume":"22","author":"H Edelsbrunner","year":"1982","unstructured":"Edelsbrunner, H., Maurer, H.A., Preparata, F.P., Rosenberg, A.L., Welzl, E., Wood, D.: Stabbing line segments. BIT Numer. Math. 22(3), 274\u2013281 (1982)","journal-title":"BIT Numer. Math."},{"issue":"1","key":"1311_CR16","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 Compt. Geometry 1(1), 25\u201344 (1986)","journal-title":"Discrete Compt. Geometry"},{"key":"1311_CR17","doi-asserted-by":"crossref","unstructured":"Guo, T., Cao, X., Cong, G.: Efficient algorithms for answering the m-closest keywords query. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (PODS\u201915). pp. 405\u2013418. (2015)","DOI":"10.1145\/2723372.2723723"},{"issue":"3","key":"1311_CR18","doi-asserted-by":"publisher","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 Compt. Geometry 9(3), 267\u2013291 (1993). https:\/\/doi.org\/10.1007\/BF02189323","journal-title":"Discrete Compt. Geometry"},{"key":"1311_CR19","doi-asserted-by":"publisher","unstructured":"Iacono, J., Khramtcova, E., Langerman, S.: Searching edges in the overlap of two plane graphs. In: Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017). pp. 473\u2013484. Springer (2017). https:\/\/doi.org\/10.1007\/978-3-319-62127-2_40","DOI":"10.1007\/978-3-319-62127-2_40"},{"key":"1311_CR20","doi-asserted-by":"publisher","unstructured":"J\u00f8rgensen, A., L\u00f6ffler, M., Phillips, J.M.: Geometric computations on indecisive points. In: Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011). pp. 536\u2013547. Springer (2011). https:\/\/doi.org\/10.1007\/978-3-642-22300-6_45","DOI":"10.1007\/978-3-642-22300-6_45"},{"key":"1311_CR21","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. Springer Science & Business Media, Cham (1989). https:\/\/doi.org\/10.1007\/3-540-52055-4"},{"issue":"6","key":"1311_CR22","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1016\/j.adhoc.2013.03.005","volume":"11","author":"C Lee","year":"2013","unstructured":"Lee, C., Shin, D., Bae, S.W., Choi, S.: Best and worst-case coverage problems for arbitrary paths in wireless sensor networks. Ad Hoc Netw. 11(6), 1699\u20131714 (2013). https:\/\/doi.org\/10.1016\/j.adhoc.2013.03.005","journal-title":"Ad Hoc Netw."},{"key":"1311_CR23","doi-asserted-by":"publisher","unstructured":"Mantas, I., Papadopoulou, E., Sacrist\u00e1n, V., Silveira, R.I.: Farthest color Voronoi diagrams: complexity and algorithms. In: Proceedings of the 14th Latin American Symposium on Theoretical Informatics (LATIN 2020). LNCS, vol. 12118, pp. 283\u2013295. Springer (2021). https:\/\/doi.org\/10.1007\/978-3-030-61792-9_23","DOI":"10.1007\/978-3-030-61792-9_23"},{"issue":"06","key":"1311_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. Geometry Appl. 11(06), 583\u2013616 (2001). https:\/\/doi.org\/10.1142\/S0218195901000663","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"1311_CR25","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, 2nd edn. Wiley, Hoboken (2000)","edition":"2"},{"issue":"2","key":"1311_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). https:\/\/doi.org\/10.1007\/s00453-004-1095-0","journal-title":"Algorithmica"},{"issue":"5","key":"1311_CR27","doi-asserted-by":"publisher","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 T. Comput. Aid. D. 30(5), 704\u2013716 (2011)","journal-title":"IEEE T. Comput. Aid. D."},{"issue":"06","key":"1311_CR28","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1142\/S0218195913600121","volume":"23","author":"E Papadopoulou","year":"2013","unstructured":"Papadopoulou, E., Dey, S.K.: On the farthest line-segment Voronoi diagram. Int. J. Comput. Geometry Appl. 23(06), 443\u2013459 (2013)","journal-title":"Int. J. Comput. Geometry Appl."},{"issue":"06","key":"1311_CR29","doi-asserted-by":"publisher","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. Geometry Appl. 14(06), 421\u2013452 (2004). https:\/\/doi.org\/10.1142\/S0218195904001536","journal-title":"Int. J. Comput. Geometry Appl."},{"key":"1311_CR30","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer-Verlag New York Inc, New York (1985). https:\/\/doi.org\/10.1007\/978-1-4612-1098-6"},{"key":"1311_CR31","unstructured":"Voronoi CAA: Voronoi Critical Area Analysis. IBM CAD Tool, Department of Electronic Design Automation, IBM Microelectronics Division, Burlington, VT, patents: US6178539, US6317859, US7240306, US7240306, US20080168414, US20090031263"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01311-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01311-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01311-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T23:02:33Z","timestamp":1757026953000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01311-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,6]]},"references-count":31,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["1311"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01311-1","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-4644060\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,6]]},"assertion":[{"value":"26 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}