A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation |
| |
Authors: | Banghe Li Bo Li |
| |
Affiliation: | a Center of Bioinformatics & Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100080, China b Graduate University of Chinese Academy of Sciences, Beijing 100049, China |
| |
Abstract: | To determine the similarity of two point sets is one of the major goals of pattern recognition and computer graphics. One widely studied similarity measure for point sets is the Hausdorff distance. So far, various computational methods have been proposed for computing the minimum Hausdorff distance. In this paper, we propose a new algorithm to compute the minimum Hausdorff distance between two point sets on a line under translation, which outperforms other existing algorithms in terms of efficiency despite its complexity of O((m+n)lg(m+n)), where m and n are the sizes of two point sets. |
| |
Keywords: | Hausdorff distance Pattern recognition Computational geometry |
本文献已被 ScienceDirect 等数据库收录! |
|