Ludmila Scharf

Computing the Hausdorff distance between sets of curves

Betreuer: Prof. Dr. Helmut Alt
Abschluss: Diplom
Abgabedatum: 01.01.2004
Homepage des Autors:


Abstract: This paper describes an algorithm for computation of the Hausdorff distance between sets of plane algebraic rational parametric curves. The Hausdorff distance is one of the frequently used similarity measures in geometric pattern matching algorithms. It is defined for arbitrary non-empty bounded and closed sets A and B. Hausdorff distance assigns to each point of one set the distance to its closest point on the other and takes the maximum over all these values. We work with Euclidean distance as point to point distance measure.

The algorithm presented here is restricted to the curves with rational parameterization and no poles on the defining interval. We also describe a polygon line approximation algorithm, based on Douglas-Peucker polygon line simplification algorithm.