The problem of geometric point set matching has been well-studied in the domain of computational geometry, and it has many applications in areas such as computer vision, computational chemistry, and pattern recognition. One of the commonly used metrics is the bottleneck matching distance, which is the minimum length of the longest edge in a one-to-one mapping between two point sets. Much effort has gone into developing efficient algorithms for minimising the bottleneck distance between two point sets under groups of transformations. However, the algorithms that have thus far been developed suffer from running times that are large polynomials in the size of the input, even for approximate formulations of the problem.
In this paper we present near-linear time approximation schemes for minimising the bottleneck distance between two point sets under translations, that run in near-linear time. These schemes relax the condition that the mapping must be one-to-one, but guarantee that not too many points are mapped to any point. Our techniques involve an interesting application of Hall's Theorem to reduce the geometric matching problem to a combinatorial matching problem, and a combinatorial bound on the metric entropy of a certain family of geometric objects.