Partial-Matching RMS Distance Under Translation: Combinatorics and Algorithms

Ben-Avraham, R. and Henze, M. and Jaume, R. and Keszegh, Balázs and Raz, O. E. (2017) Partial-Matching RMS Distance Under Translation: Combinatorics and Algorithms. ALGORITHMICA. pp. 1-22. ISSN 0178-4617 (In Press)

Preview

Text 1411.7273v1.pdf Download (545kB) | Preview

Abstract

We consider the problem of minimizing the RMS distance (sum of squared distances between pairs of points) under translation between two point sets A and B, in the plane, with (Formula presented.), in the partial-matching setup, in which each point in B is matched to a distinct point in A. Although the problem is not known to be polynomial, we establish several structural properties of the underlying subdivision (Formula presented.) of the plane and derive improved bounds on its complexity. Specifically, we show that this complexity is (Formula presented.), so it is only quadratic in |A|. 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. © 2017 Springer Science+Business Media New York

Actions (login required)

Edit Item