Approximate Congruence in Near-Linear Time


Consider two point sets P and Q in the plane, and a v-to-one mapping f from P to Q. Let the cost of such a mapping be the length of the longest edge in the mapping defined by f, i.e., c(f) = max_{p \in P} |p - f(p)|. Define generalized bottleneck distance between two point sets to be min_f c(f).

We will consider the problem of finding the generalized bottleneck distance between two points sets under translations, and the ideas of Piotr Indyk and Suresh Venkatasubramanian on solving this problem.