Computing the Hausdorff distance of geometric patterns and shapes. (English) Zbl 1104.68792
Aronov, Boris (ed.) et al., Discrete and computational geometry. The Goodman-Pollack Festschrift. Berlin: Springer (ISBN 3-540-00371-1/hbk). Algorithms Comb. 25, 65-76 (2003).
Summary: A very natural distance measure for comparing shapes and patterns is the Hausdorff distance. In this article we develop algorithms for computing the Hausdorff distance in a very general case in which geometric objects are represented by finite collections of -dimensional simplices in -dimensional space. The algorithms are polynomial in the size of the input, assuming is a constant. In addition, we present more efficient algorithms for special cases like sets of points, or line segments, or triangulated surfaces in three dimensions.
|68U05||Computer graphics; computational geometry|