Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Lower bounds for the complexity of the Hausdorff distance
Authors: Rucklidge, William J.
Keywords: computer science
technical report
Issue Date: Aug-1994
Publisher: Cornell University
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.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
94-1441.pdf2.92 MBAdobe PDFView/Open
94-1441.ps1.6 MBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us