Approximate congruence in nearly linear time (Q1869745)

Generalized bottleneck distance is defined as a point set distance measure that includes as special cases the bottleneck distance and the Hausdorff distance. The new formulation allows to achieve a tradeoff between the quality of match (guarantees that only a few points are mapped to any point) and the complexity of the matching procedures (near-linear time approximation schemes for minimizing the distance between two point sets in the plane under isometries). The results are based on the reduction of the geometric matching to combinatorial pattern matching. Supplementary, it is obtained a combinatorial bound on the metric entropy of certain families of geometric objects.