transformations between point sets with no correspondence

Another problem that arises frequently in computer vision applications is finding a transformation that maps one set of points to another, where we have no information about point correspondences.

For instance, suppose I have a corner detector, and I want to align the set of detected corners to a floor plan, perhaps for an application like this one.

In addition, as will nearly always be the case, many of my detected corners are spurious. What I want to do is find a transformation that maps as many detected corners as possible to corners on the floor plan.

Unfortunately, even an extremely simplified version of this problem is thought to be hard, where hard means there is no solution better than quadratic. This implies that to find the exact solution, we will have to look at each pair of a detected corner and a floor plan corner.

Here's the simplified version: given two sets of numbers A and B, find the constant offset c that we can add to all elements of A to maximize the number of elements that A and B have in common. In other words, considering points in 1D, what is the translation that maximizes the number of correspondences?

It turns out that this problem is hard even if we are merely trying to detect whether or not there are two correspondences that agree on a translation. This is shown through a reduction to the 3SUM problem in this paper.