{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T04:10:20Z","timestamp":1758946220654,"version":"3.44.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:00:00Z","timestamp":1756425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T00:00:00Z","timestamp":1756425600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["2230534 IF\/R","2230534 IF\/R","2230534 IF\/R","2230534 IF\/R"],"award-info":[{"award-number":["2230534 IF\/R","2230534 IF\/R","2230534 IF\/R","2230534 IF\/R"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo,Chile","award":["2130520 IF\/R","2130520 IF\/R","2130520 IF\/R","2130520 IF\/R"],"award-info":[{"award-number":["2130520 IF\/R","2130520 IF\/R","2130520 IF\/R","2130520 IF\/R"]}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1230647.","1230647.","1230647.","1230647."],"award-info":[{"award-number":["1230647.","1230647.","1230647.","1230647."]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["MCIN\/AEI\/10.13039\/501100011033"],"award-info":[{"award-number":["MCIN\/AEI\/10.13039\/501100011033"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NextGenerationEU,European Union","award":["TED2021-129245B-C21"],"award-info":[{"award-number":["TED2021-129245B-C21"]}]},{"DOI":"10.13039\/100031478","name":"NextGenerationEU","doi-asserted-by":"publisher","award":["PID2020-114635RB-I00"],"award-info":[{"award-number":["PID2020-114635RB-I00"]}],"id":[{"id":"10.13039\/100031478","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010556","name":"Conseller\u00eda de Econom\u00eda, Emprego e Industria, Xunta de Galicia","doi-asserted-by":"publisher","award":["ED431C 2021\/53"],"award-info":[{"award-number":["ED431C 2021\/53"]}],"id":[{"id":"10.13039\/501100010556","id-type":"DOI","asserted-by":"publisher"}]},{"name":"European Regional Development Fund,European Union","award":["ED431G 2023\/01"],"award-info":[{"award-number":["ED431G 2023\/01"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Geoinformatica"],"published-print":{"date-parts":[[2025,10]]},"DOI":"10.1007\/s10707-025-00557-9","type":"journal-article","created":{"date-parts":[[2025,8,29]],"date-time":"2025-08-29T04:45:00Z","timestamp":1756442700000},"page":"1067-1092","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient algorithms to calculate the Hausdorff distance on point sets represented by a $$k^2\\text {-tree}$$"],"prefix":"10.1007","volume":"29","author":[{"given":"Fernando","family":"Dom\u00ednguez","sequence":"first","affiliation":[]},{"given":"Gilberto","family":"Guti\u00e9rrez","sequence":"additional","affiliation":[]},{"given":"Miguel R.","family":"Penabad","sequence":"additional","affiliation":[]},{"given":"Miguel","family":"Romero","sequence":"additional","affiliation":[]},{"given":"Fernando","family":"Santolaya","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,29]]},"reference":[{"key":"557_CR1","volume-title":"General Topology","author":"JL Kelley","year":"1975","unstructured":"Kelley JL (1975) General Topology. Springer, New York, NY, USA"},{"issue":"4","key":"557_CR2","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0020-0190(83)90042-X","volume":"17","author":"MJ Atallah","year":"1983","unstructured":"Atallah MJ (1983) A linear time algorithm for the Hausdorff distance between convex polygons. Inf Process Lett 17(4):207\u2013209","journal-title":"Inf Process Lett"},{"issue":"8","key":"557_CR3","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1016\/j.cagd.2010.04.004","volume":"27","author":"M Barto\u0148","year":"2010","unstructured":"Barto\u0148 M, Hanniel I, Elber G, Kim M-S (2010) Precise Hausdorff distance computation between polygonal meshes. Comput Aided Geometric Des 27(8):580\u2013591","journal-title":"Comput Aided Geometric Des"},{"key":"557_CR4","doi-asserted-by":"crossref","unstructured":"Spyridonos P, Gaitanis G, Bassukas ID, Tzaphlidou M (2013) Gray Hausdorff distance measure for medical image comparison in dermatology: Evaluation of treatment effectiveness by image similarity. Skin Res Technol 19(1)","DOI":"10.1111\/srt.12001"},{"issue":"12","key":"557_CR5","doi-asserted-by":"publisher","first-page":"1873","DOI":"10.1016\/S0031-3203(98)00076-4","volume":"31","author":"B Takacs","year":"1998","unstructured":"Takacs B (1998) Comparing face images using the modified Hausdorff distance. Pattern Recognition 31(12):1873\u20131881","journal-title":"Pattern Recognition"},{"issue":"6","key":"557_CR6","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1049\/ip-vis:20030805","volume":"150","author":"Y Gao","year":"2003","unstructured":"Gao Y (2003) Efficiently comparing face images using a modified Hausdorff distance. IEE Proceed-Vision, Image and Signal Process 150(6):346\u2013350","journal-title":"IEE Proceed-Vision, Image and Signal Process"},{"key":"557_CR7","doi-asserted-by":"crossref","unstructured":"Jesorsky O, Kirchberg KJ, Frischholz RW (2001) Robust face detection using the Hausdorff distance. In: International conference on audio-and video-based biometric person authentication, Springer, pp 90\u201395","DOI":"10.1007\/3-540-45344-X_14"},{"issue":"11","key":"557_CR8","doi-asserted-by":"publisher","first-page":"2153","DOI":"10.1109\/TPAMI.2015.2408351","volume":"37","author":"AA Taha","year":"2015","unstructured":"Taha AA, Hanbury A (2015) An efficient algorithm for calculating the exact Hausdorff distance. IEEE Trans Pattern Anal Mach Intell 37(11):2153\u20132163","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"8","key":"557_CR9","doi-asserted-by":"publisher","first-page":"506","DOI":"10.14778\/2002974.2002978","volume":"4","author":"S Nutanong","year":"2011","unstructured":"Nutanong S, Jacox EH, Samet H (2011) An incremental Hausdorff distance calculation algorithm. Proceed VLDB Endowment 4(8):506\u2013517","journal-title":"Proceed VLDB Endowment"},{"key":"557_CR10","doi-asserted-by":"crossref","unstructured":"Trajcevski G, Ding H, Scheuermann P, Tamassia R, Vaccaro D (2007) Dynamics-aware similarity of moving objects trajectories. In: Proceedings of the 15th Annual ACM international symposium on advances in geographic information systems, ACM, pp 11","DOI":"10.1145\/1341012.1341027"},{"key":"557_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures: A Practical Approach","author":"G Navarro","year":"2016","unstructured":"Navarro G (2016) Compact Data Structures: A Practical Approach, 1st edn. Cambridge University Press, New York, NY, USA","edition":"1"},{"key":"557_CR12","doi-asserted-by":"crossref","unstructured":"Navarro G (2012) Wavelet trees for all. In: Annual symposium on combinatorial pattern matching, Springer, pp 2\u201326","DOI":"10.1007\/978-3-642-31265-6_2"},{"key":"557_CR13","unstructured":"Ladra\u00a0Gonz\u00e1lez S (2011) Algorithms and compressed data structures for information retrieval. PhD thesis, Universidade da Coruna"},{"key":"557_CR14","doi-asserted-by":"publisher","unstructured":"Dom\u00ednguez F, Gutierrez G, Romero M (2018) Algorithm to calculate the Hausdorff Distance on sets of points represented by k2-tree. In: 2018 XLIV Latin American computer conference (CLEI), pp 482\u2013489. https:\/\/doi.org\/10.1109\/CLEI.2018.00064","DOI":"10.1109\/CLEI.2018.00064"},{"key":"557_CR15","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.tcs.2021.09.012","volume":"892","author":"F Santolaya","year":"2021","unstructured":"Santolaya F, Caniup\u00e1n M, Gajardo L, Romero M, Torres-Avil\u00e9s R (2021) Efficient computation of spatial queries over points stored in k2-tree compact data structures. Theoretical Comput Sci 892:108\u2013131. https:\/\/doi.org\/10.1016\/j.tcs.2021.09.012","journal-title":"Theoretical Comput Sci"},{"key":"557_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.is.2018.10.001","volume":"80","author":"C Quijada-Fuentes","year":"2019","unstructured":"Quijada-Fuentes C, Penabad MR, Ladra S, Guti\u00e9rrez G (2019) Set operations over compressed binary relations. Inf Syst 80:76\u201390","journal-title":"Inf Syst"},{"issue":"3","key":"557_CR17","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/1531326.1531380","volume":"28","author":"M Tang","year":"2009","unstructured":"Tang M, Lee M, Kim YJ (2009) Interactive Hausdorff distance computation for general polygonal models. ACM Trans Graphics (TOG) 28(3):74","journal-title":"ACM Trans Graphics (TOG)"},{"key":"557_CR18","doi-asserted-by":"crossref","unstructured":"Alt H, Behrends B, Bl\u00f6mer J (1991) Approximate matching of polygonal shapes. In: Proceedings of the seventh annual symposium on computational geometry, ACM, pp 186\u2013193","DOI":"10.1145\/109648.109669"},{"key":"557_CR19","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.patcog.2017.02.013","volume":"67","author":"Y Chen","year":"2017","unstructured":"Chen Y, He F, Wu Y, Hou N (2017) A local start search algorithm to compute exact Hausdorff distance for arbitrary point sets. Pattern Recognition 67:139\u2013148","journal-title":"Pattern Recognition"},{"issue":"2","key":"557_CR20","first-page":"41","volume":"13","author":"M Guthe","year":"2005","unstructured":"Guthe M, Borodin P, Klein R (2005) Fast and accurate Hausdorff distance calculation between meshes. J WSCG 13(2):41\u201348","journal-title":"J WSCG"},{"issue":"2","key":"557_CR21","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0146-664X(82)90104-6","volume":"19","author":"D Meagher","year":"1982","unstructured":"Meagher D (1982) Geometric modeling using octree encoding. Comput Graphics Image Process 19(2):129\u2013147","journal-title":"Comput Graphics Image Process"},{"key":"557_CR22","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.cagd.2018.03.017","volume":"62","author":"Y Kang","year":"2018","unstructured":"Kang Y, Kyung M-H, Yoon S-H, Kim M-S (2018) Fast and robust Hausdorff distance computation from triangle mesh to quad mesh in near-zero cases. Comput Aided Geometric Des 62:91\u2013103","journal-title":"Comput Aided Geometric Des"},{"key":"557_CR23","doi-asserted-by":"publisher","first-page":"1350","DOI":"10.1109\/ACCESS.2017.2778745","volume":"6","author":"D Zhang","year":"2018","unstructured":"Zhang D, Zou L, Chen Y, He F (2018) Efficient and accurate Hausdorff distance computation based on diffusion search. IEEE Access 6:1350\u20131361","journal-title":"IEEE Access"},{"key":"557_CR24","volume-title":"A computer oriented geodetic data base and a new technique in file sequencing","author":"GM Morton","year":"1966","unstructured":"Morton GM (1966) A computer oriented geodetic data base and a new technique in file sequencing. Technical report, IBM Ltd, Ottawa, Canada"},{"key":"557_CR25","doi-asserted-by":"crossref","unstructured":"Huttenlocher DP, Kedem K (1990) Computing the minimum Hausdorff distance for point sets under translation. In: Proceedings of the sixth annual symposium on computational geometry, ACM, pp 340\u2013349","DOI":"10.1145\/98524.98599"},{"issue":"3","key":"557_CR26","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(91)90233-8","volume":"38","author":"G Rote","year":"1991","unstructured":"Rote G (1991) Computing the minimum Hausdorff distance between two point sets on a line under translation. Inf Process Lett 38(3):123\u2013127","journal-title":"Inf Process Lett"},{"issue":"2","key":"557_CR27","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.ipl.2007.10.003","volume":"106","author":"B Li","year":"2008","unstructured":"Li B, Shen Y, Li B (2008) A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation. Inf Process Lett 106(2):52\u201358","journal-title":"Inf Process Lett"},{"key":"557_CR28","doi-asserted-by":"crossref","unstructured":"Chang F, Chen Z, Wang W, Wang L (2009) The Hausdorff distance template matching algorithm based on Kalman filter for target tracking. In: Automation and Logistics, 2009. ICAL\u201909. IEEE International Conference On, IEEE, pp 836\u2013840","DOI":"10.1109\/ICAL.2009.5262808"},{"issue":"1","key":"557_CR29","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1115\/1.3662552","volume":"82","author":"RE Kalman","year":"1960","unstructured":"Kalman RE (1960) A new approach to linear filtering and prediction problems. J Basic Eng 82(1):35\u201345","journal-title":"J Basic Eng"},{"key":"557_CR30","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2021.107857","volume":"114","author":"J Ryu","year":"2021","unstructured":"Ryu J, Kamata S-i (2021) An efficient computational algorithm for Hausdorff distance based on points-ruling-out and systematic random sampling. Pattern Recognition 114:107857. https:\/\/doi.org\/10.1016\/j.patcog.2021.107857","journal-title":"Pattern Recognition"},{"issue":"12","key":"557_CR31","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1016\/j.cad.2010.06.009","volume":"42","author":"X-D Chen","year":"2010","unstructured":"Chen X-D, Ma W, Xu G, Paul J-C (2010) Computing the Hausdorff distance between two B-spline curves. Comput-Aided Design 42(12):1197\u20131206","journal-title":"Comput-Aided Design"},{"key":"557_CR32","doi-asserted-by":"crossref","unstructured":"Brisaboa NR, Ladra S, Navarro G (2009) k2-trees for compact web graph representation. In: International symposium on string processing and information retrieval, Springer, pp 18\u201330","DOI":"10.1007\/978-3-642-03784-9_3"},{"issue":"2","key":"557_CR33","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H Samet","year":"1984","unstructured":"Samet H (1984) The quadtree and related hierarchical data structures. ACM Comput Surv (CSUR) 16(2):187\u2013260","journal-title":"ACM Comput Surv (CSUR)"},{"key":"557_CR34","doi-asserted-by":"crossref","unstructured":"\u00c1lvarez-Garc\u00eda S, Freire\u00a0CB, Ladra S, Pedreira O (2018) Compact and efficient representation of general graph databases. Knowl Inf Syst 1\u201332","DOI":"10.1007\/s10115-018-1275-x"},{"key":"557_CR35","unstructured":"Bernardo\u00a0Roca G (2014) New data structures and algorithms for the efficient management of large spatial datasets. PhD thesis, Universidade da Coruna"},{"key":"557_CR36","doi-asserted-by":"crossref","unstructured":"Bernardo G, \u00c1lvarez-Garc\u00eda S, Brisaboa NR, Navarro G, Pedreira O (2013) Compact querieable representations of raster data. In: Procs. of SPIRE, pp 96\u2013108","DOI":"10.1007\/978-3-319-02432-5_14"},{"key":"557_CR37","doi-asserted-by":"crossref","unstructured":"Brisaboa NR, Ladra S, Navarro G (2014) Compact representation of web graphs with extended functionality. Inf Syst 152\u2013174","DOI":"10.1016\/j.is.2013.08.003"},{"key":"557_CR38","doi-asserted-by":"publisher","unstructured":"Guttman A (1984) R-trees: A dynamic index structure for spatial searching. In: 1984 ACM SIGMOD international conference on management of data, SIGMOD 1984, pp 47\u201357. https:\/\/doi.org\/10.1145\/602259.602266","DOI":"10.1145\/602259.602266"},{"issue":"9","key":"557_CR39","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley JL (1975) Multidimensional binary search trees used for associative searching. Commun ACM 18(9):509\u2013517. https:\/\/doi.org\/10.1145\/361002.361007","journal-title":"Commun ACM"},{"issue":"1","key":"557_CR40","first-page":"50","volume":"4","author":"RA Brown","year":"2015","unstructured":"Brown RA (2015) Building a balanced $$k$$-d tree in $$o(kn \\log n)$$ time. J Comput Graphics Techniques (JCGT) 4(1):50\u201368","journal-title":"J Comput Graphics Techniques (JCGT)"},{"key":"557_CR41","doi-asserted-by":"publisher","unstructured":"Corral A, Manolopoulos Y, Theodoridis Y, Vassilakopoulos M (2000) Closest pair queries in spatial databases. In: Proceedings of the 2000 ACM SIGMOD international conference on management of data. SIGMOD \u201900, pp. 189\u2013200. ACM, New York, NY, USA. https:\/\/doi.org\/10.1145\/342009.335414","DOI":"10.1145\/342009.335414"},{"issue":"2","key":"557_CR42","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/568271.223794","volume":"24","author":"N Roussopoulos","year":"1995","unstructured":"Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. SIGMOD Rec 24(2):71\u201379. https:\/\/doi.org\/10.1145\/568271.223794","journal-title":"SIGMOD Rec"},{"issue":"2","key":"557_CR43","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1145\/335191.335414","volume":"29","author":"A Corral","year":"2000","unstructured":"Corral A, Manolopoulos Y, Theodoridis Y, Vassilakopoulos M (2000) Closest pair queries in spatial databases. SIGMOD Rec 29(2):189\u2013200. https:\/\/doi.org\/10.1145\/335191.335414","journal-title":"SIGMOD Rec"},{"issue":"1","key":"557_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.datak.2005.03.004","volume":"57","author":"A Corral","year":"2006","unstructured":"Corral A, Manolopoulos Y, Theodoridis Y, Vassilakopoulos M (2006) Cost models for distance joins queries using R-trees. Data Knowl Eng 57(1):1\u201336","journal-title":"Data Knowl Eng"},{"key":"557_CR45","doi-asserted-by":"crossref","unstructured":"Agenis-Nevers M, Bokde ND, Yaseen ZM, Shende M (2020) An empirical estimation for time and memory algorithm complexities: Newly developed R package. arXiv:1911.01420","DOI":"10.1007\/s11042-020-09471-8"},{"key":"557_CR46","doi-asserted-by":"publisher","unstructured":"Goldsmith SF, Aiken AS, Wilkerson DS (2007) Measuring empirical computational complexity. In: Proceedings of the the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering. ESEC-FSE \u201907, pp. 395\u2013404. Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/1287624.1287681","DOI":"10.1145\/1287624.1287681"},{"key":"557_CR47","doi-asserted-by":"publisher","unstructured":"G\u00f3mez Brand\u00f3n A (2021) Object Trajectories figshare. https:\/\/doi.org\/10.6084\/m9.figshare.c.5740388.v2. https:\/\/figshare.com\/articles\/collection\/Object_Trajectories\/5740388\/2","DOI":"10.6084\/m9.figshare.c.5740388.v2"}],"container-title":["GeoInformatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-025-00557-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10707-025-00557-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10707-025-00557-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T03:54:57Z","timestamp":1758945297000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10707-025-00557-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,29]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["557"],"URL":"https:\/\/doi.org\/10.1007\/s10707-025-00557-9","relation":{},"ISSN":["1384-6175","1573-7624"],"issn-type":[{"type":"print","value":"1384-6175"},{"type":"electronic","value":"1573-7624"}],"subject":[],"published":{"date-parts":[[2025,8,29]]},"assertion":[{"value":"3 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2025","order":4,"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":"Competing interests"}}]}}