APPROXIMATE NEAREST NEIGHBOR SEARCH UNDER TRANSLATION IN VARIANT HAUSDORFF DISTANCE

作者：Knauer Christian^*; Scherfenberg Marc

来源：International Journal of Computational Geometry and Applications, 2011, 21(3): 369-381.

DOI：10.1142/S0218195911003706

• Computational geometry
• image retrieval
• nearest neighbor search
• shape matching
• directed Hausdorff distance
• point patterns
• data structure

We present an embedding and search reduction which allow us to build the first data structure for the nearest neighbor search among small point sets with respect to the directed Hausdorff distance under translation. The search structure is non-heuristic in the sense that the quality of the results, the performance, and the space bound are guaranteed.
Let n denote the number of point sets in the database, s the maximal size of a point set, and d the dimension of the points. The nearest neighbor of a query point set under the translation invariant directed Hausdorff distance can be approximated by one or several nearest neighbor searches for single points in the Euclidean embedding space Rd(s-1) . The approximation factor is root ds/2 in case of even s and root d(s - 1/s)/2 when s is odd. Depending on the direction of the Hausdorff distance either the number of queries or the space requirements are exponential in s.
Furthermore it is shown how to find the exact nearest neighbor under the directed Hausdorff distance without transformation of the point sets within some weaker time and space bounds.

• 出版日期2011-6