On bipartite matching under the RMS distance

Published

Conference Paper

© 2006 Canadian Conference on Computational Geometry. All rights reserved. Given two sets A and B of n points each in R2, 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(n2+δ) time, for any δ > 0, and an ε-approximation in time O((n/ε)3/2 log6 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((n4/ε5/2) log6 n) time whose cost is within (1 + ε) factor of the optimal one.

Duke Authors

Cited Authors

  • Agarwal, PK; Phillips, JM

Published Date

  • January 1, 2006

Published In

  • Proceedings of the 18th Annual Canadian Conference on Computational Geometry, Cccg 2006

Start / End Page

  • 143 - 146

Citation Source

  • Scopus