# 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