JavaScript is disabled for your browser. Some features of this site may not work without it.
Lower bounds for the complexity of the Hausdorff distance

Author
Rucklidge, William J.
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.
Date Issued
1994-08Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR94-1441
Type
technical report