On Bipartite Matching under the RMS Distance
Jeff M. Phillips, Pankaj K. Agarwal · Canadian Conference on Computational Geometry · 2006
Given two sets A and B of n points each in R 2 , we study the problem of computing a matching between A and B that minimizes the root mean square (rms) distance of matched pairs. We can compute an optimal matching in O(n 2+! ) time, for any ! > 0, and an -approximation in time O((n/ ) 3/2 log 6 n). If the set B is allowed to move rigidly to minimize the rms distance, we can compute a rigid motion of B and a matching in O((n 4 / 5/2 )log 6 n) time whose cost is within (1 + ) factor of the optimal one.