APPROXIMATE NEAREST NEIGHBOR SEARCH UNDER TRANSLATION IN VARIANT HAUSDORFF DISTANCE
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 R(d(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.
nearest neighbor search data structure directed hausdorff distance computational geometry image retrieval shape matching point patterns