TY - GEN

T1 - Algorithm to calculate the hausdorff distance on sets of points represented by k2-Tree

AU - Gutierrez, Gilberto

AU - Romero, Miguel

AU - Dominguez, Fernando

N1 - Publisher Copyright:
© 2018 IEEE.

PY - 2018/10

Y1 - 2018/10

N2 - The Hausdorff distance between two sets of points A and B corresponds to the largest of the distances between each object x ϵ A and its nearest neighbor in B. The Hausdorff distance has several applications, such as comparing medical images or comparing two transport routes. There are different algorithms to compute the Hausdorff distance, some operate with the sets of points in main memory and others in secondary memory. On the other hand, to face the challenge of indexing large sets of points in main memory, there are compact data structures such as k2-Tree which, by minimizing storage, can be efficiently consulted. An efficient algorithm (HDK2) that allows the calculation of the Hausdorff distance in the compact structure k2-Tree is presented in this article. This algorithm achieves an efficient solution in both time and space. Through a series of experiments, the performance of our algorithm was evaluated together with others proposed in literature under similar conditions. The results allow to conclude that HDK2 has a better performance in runtime than such algorithms.

AB - The Hausdorff distance between two sets of points A and B corresponds to the largest of the distances between each object x ϵ A and its nearest neighbor in B. The Hausdorff distance has several applications, such as comparing medical images or comparing two transport routes. There are different algorithms to compute the Hausdorff distance, some operate with the sets of points in main memory and others in secondary memory. On the other hand, to face the challenge of indexing large sets of points in main memory, there are compact data structures such as k2-Tree which, by minimizing storage, can be efficiently consulted. An efficient algorithm (HDK2) that allows the calculation of the Hausdorff distance in the compact structure k2-Tree is presented in this article. This algorithm achieves an efficient solution in both time and space. Through a series of experiments, the performance of our algorithm was evaluated together with others proposed in literature under similar conditions. The results allow to conclude that HDK2 has a better performance in runtime than such algorithms.

KW - Algorithms

KW - Compact Data Structures

KW - Hausdorff distance

KW - K2-Tree

UR - http://www.scopus.com/inward/record.url?scp=85071144242&partnerID=8YFLogxK

U2 - 10.1109/CLEI.2018.00064

DO - 10.1109/CLEI.2018.00064

M3 - Conference contribution

AN - SCOPUS:85071144242

T3 - Proceedings - 2018 44th Latin American Computing Conference, CLEI 2018

SP - 482

EP - 489

BT - Proceedings - 2018 44th Latin American Computing Conference, CLEI 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 44th Latin American Computing Conference, CLEI 2018

Y2 - 1 October 2018 through 5 October 2018

ER -