Details

Autor(en) / Beteiligte

• Ben-Avraham, Rinat
• Henze, Matthias
• Jaume, Rafel
• Keszegh, Balázs
• Raz, Orit E.
• Sharir, Micha
• Tubis, Igor

Titel

Partial-Matching RMS Distance Under Translation: Combinatorics and Algorithms

Ist Teil von

• Algorithmica, 2018-08, Vol.80 (8), p.2400-2421

Ort / Verlag

New York: Springer US

Erscheinungsjahr

2018

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 m = | B | ≪ n = | A | , 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 D B , A of the plane and derive improved bounds on its complexity. Specifically, we show that this complexity is O ( n 2 m 3.5 ( e ln m + e ) m ) , 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.