Lower bounds for the complexity of the graph of the Hausdorff distance as a function of transformation

The Hausdorff distance is a measure defined between two sets in some metric space. This paper investigates how the Hausdorff distance changes as one set is transformed by some transformation group. Algorithms to find the minimum distance as one set is transformed have been described, but few lower bounds are known. We consider the complexity of the graph of the Hausdorff distance as a function of transformation, and exhibit some constructions that give lower bounds for this complexity. We exhibit lower-bound constructions for both sets of points in the plane, and sets of points and line segments; we consider the graph of the directed Hausdorff distance under translation, rigid motion, translation and scaling, and affine transformation. Many of the results can also be extended to the undirected Hausdorff distance. These lower bounds are for the complexity of the graph of the Hausdorff distance, and thus do not necessarily bound algorithms that search this graph; however, they do give an indication of how complex the search may be. This work was supported in part by National Science Foundation PYI Grant IRI-9057928 and matching funds from General Electric, Kodak, and Xerox, and in part by Air Force Contract AFOSR-91-0328.