Geometric pattern matching in d-dimensional space

We show that, using the L-infinity metric, the minimum Hausdorff distance u nder translation between two point sets of cardinality n in d-dimensional s pace can be computed in time O(n((4d-2)/3) log(2) n) for 3 < d less than or equal to 8, and in time O(n(5d/4) log(2) n) for any d > 8. Thus we improve the previous time bound of O(n(2d-2) log(2) n) due to Chew and Kedem. For d = 3 we obtain a better result of O (n(3) log(2) n) time by exploiting the fact that the union of n axis-parallel unit cubes can be decomposed into O (n) disjoint axis-parallel boxes. We prove that the number of different tra nslations that achieve the minimum Hausdorff distance in d-space is Theta(n ([3d/2])). Furthermore, we present an algorithm which computes the minimum Hausdorff distance under the L-2 metric in d-space in time O (n([3d/2]+1+de lta)), for any delta > 0.