Partial-Matching RMS Distance Under Translation: Combinatorics and Algorithms.

We consider the problem of minimizing the RMS distance (sum of squared distances between pairs of points) under translation between two point sets <italic>A</italic> and <italic>B</italic>, in the plane, with m=|B|≪n=|A|<inline-graphic></inline-graphic>, in the partial-matching setup, in which each point in <italic>B</italic> is matched to a distinct point in <italic>A</italic>. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision DB,A<inline-graphic></inline-graphic> of the plane and derive improved bounds on its complexity. Specifically, we show that this complexity is O(n2m3.5(elnm+e)m)<inline-graphic></inline-graphic>, so it is only quadratic in |<italic>A</italic>|. These results lead to the best known algorithm for finding a translation for which the partial-matching RMS distance between the point sets is minimized. In addition, we show how to compute a local minimum of the partial-matching RMS distance under translation, in polynomial time. [ABSTRACT FROM AUTHOR]