Article ID: | iaor201113539 |
Volume: | 38 |
Issue: | 1 |
Start Page Number: | 45 |
End Page Number: | 58 |
Publication Date: | Jan 2004 |
Journal: | Algorithmica |
Authors: | Alt Helmut, Knauer Christian, Wenk Carola |
Keywords: | topology |
The Hausdorff distance is a very natural and straightforward distance measure for comparing geometric shapes like curves or other compact sets. Unfortunately, it is not an appropriate distance measure in some cases. For this reason, the Fréchet distance has been investigated for measuring the resemblance of geometric shapes which avoids the drawbacks of the Hausdorff distance. Unfortunately, it is much harder to compute. Here we investigate under which conditions the two distance measures approximately coincide, i.e., the pathological cases for the Hausdorff distance cannot occur. We show that for closed convex curves both distance measures are the same. Furthermore, they are within a constant factor of each other for so‐called κ‐straight curves, i.e., curves where the arc length between any two points on the curve is at most a constant κ times their Euclidean distance. Therefore, algorithms for computing the Hausdorff distance can be used in these cases to get exact or approximate computations of the Fréchet distance, as well.