ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. We show that, using the L ∞ metric, the minimum Hausdorff distance under translation between two point sets of cardinality n in d -dimensional space can be computed in time O(n (4d-2)/3 log 2 n) for 3 〈 d $\leq$ 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 translations that achieve the minimum Hausdorff distance in d -space is $\Theta(n^{\floor{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^{\ceil{3d/2}+1 +\delta})$ , for any δ 〉 0.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009420
Permalink
