Lower bounds for the complexity of the Hausdorff distance

Abstract

The Hausdorff distance is a similarity measure defined between sets in the plane. Algorithms to find the minimum distance as one set is transformed have been described, but few lower bounds are known. We describe new lower bounds for the complexity of the directed Hausddorff distance. We exhibit lower boundconstructions for both sets of points and sets of points and line segments, under translation, rigid motion, translation and scaling, and affine transformation. The results for point sets can also be extended to the undirected Hausdorff distance. As these lower bounds are for the complexity of the graph of the Hausdorff distance as a function of transformation, they do not necessarily bound functions which search this graph, but do give an indication of how complex the search may be.