Approximate one-to-one point pattern matching

Given a set A={a1,…,an}A={a1,…,an} of n   image points and a set B={b1,…,bn}B={b1,…,bn} of n   model points, the problem is to find a transformation matching (a one-to-one mapping) each point a∈Aa∈A to some point b∈Bb∈B such that the length of the longest edge in the matching is minimised (so-called bottleneck distance). The geometric transformations we allow are translation, rotation, reflexion and scaling. In this paper, we give (1+ε)(1+ε)-approximation algorithms for the case when the points are given in R2R2, two of which run in O(n3.5ε4logn) and O(n2.5ε4lognlogdiam(B)dopt) time, respectively, where diam(B)diam(B) is the diameter of B   and doptdopt is the bottleneck distance in an optimal matching.