Domínguez, FernandoGutiérrez, GilbertoRodríguez Penabad, MiguelRomero, MiguelSantolaya, Fernando2025-09-112025-09-112025-08-29Domínguez, F., Gutiérrez, G., Penabad, M.R. et al. Efficient algorithms to calculate the Hausdorff distance on point sets represented by a k2-tree. Geoinformatica (2025). https://doi.org/10.1007/s10707-025-00557-91573-76241384-6175https://hdl.handle.net/2183/45742This version of the article has been accepted for publication, after peer review and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10707-025-00557-9 Data used in this article was made publicly available in Zenodo: https://doi.org/10.5281/zenodo.16258820[Abstract]: The Hausdorff distance is a measure of the similarity between two sets of points. It has been used in many different fields, such as comparing MRI images or transportation routes. There have been different approaches to compute the Hausdorff distance; some algorithms operate in main memory, while others store the set of points in secondary memory. In order to avoid secondary memory, compact data structures, such as k2-tree, can be used. They are able to index large sets of points in main memory, and they can be efficiently queried while minimizing storage. We present in this article two efficient algorithms (HDKP1 and HDKP2) to compute the Hausdorff distance over two data sets that are stored in k2-trees. These algorithms provide a time- and space-efficient solution. The performance of our algorithms was evaluated through a series of experiments together with the most promising algorithms from the state of the art. Based on the results, it was concluded that our approach is competitive or exceeds current algorithms.engCopyright © 2025, The Author(s), under exclusive licence to Springer Science Business Media, LLC, part of Springer NatureAlgorithmsCompact data structuresHausdorff distancejournal articleopen access10.1007/s10707-025-00557-9