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 data base, 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 ℝ
d(s-1). The approximation factor is
in case of even s and
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.
