Comparison of Distance Measures for Planar Curves

Comparison of Distance Measures for Planar Curves

0.00 Avg rating0 Votes
Article ID: iaor201113539
Volume: 38
Issue: 1
Start Page Number: 45
End Page Number: 58
Publication Date: Jan 2004
Journal: Algorithmica
Authors: , ,
Keywords: topology
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.