Getting around a lower bound for the minimum Hausdorff distance

We consider the following geometric pattern matching problem: find the minimum Hausdorff distance between two point sets under translation with L-1 or L-infinity as the underlying metric. Huttenlocher, Kedem and Sharir have shown that this minimum distance can be found by constructing the upper envelope of certain Voronoi surfaces. Further, they show that if the two sets are each of cardinality n then the complexity of the upper envelope of such surfaces is Omega(n(3)). We examine the question of whether one can get around this cubic lower bound, and show that under the L-1 and L-infinity metrics, the time to compute the minimum Hausdorff distance between two point sets is O(n(2)log(2) n). (C) 1998 Elsevier Science B.V.