**Next:** Problem 7: k-sets

**Previous:** Problem 5: Euclidean Minimum Spanning Tree

- Statement
What is the complexity of computing a minimum-cost Euclidean matching for 2n points in the plane? The

*cost*of a matching is the total length of the edges in the matching.- Origin
Uncertain, pending investigation.

- Status/Conjectures
Open.

- Partial and Related Results
An algorithm that achieves the minimum and runs in nearly O(n^{2.5}) time has long been available [Vai89]. This was improved to O(n^{1.5} \log^5 n) in [Var98]. Recently Arora showed how to achieve a (1+\epsilon)-approximation in n (\log n)^{O(1/\epsilon)} time [Aro98], and this has been improved to O((n/\epsilon^3) \log^6 n) time [VA99].

A special case of considerable interest is bipartite matching, in which the points are red or blue and the matching connects points of different color. Here O(n^{2+\epsilon}) has been achieved [AES99], and a (1+\epsilon)-approximation can be found in O((n/\epsilon)^{1.5} \log^5 n) time [VA99].

- Appearances
- Categories
shortest paths

- Entry Revision History
J. O’Rourke, 2 Aug. 2001; 30 Aug. 2001; 13 Dec. 01 (thanks to M. Sharir).

- [Aro98]
Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.

*J. Assoc. Comput. Mach.*, 45(5):753–782, 1998.- [AES99]
P. K. Agarwal, A. Efrat, and Micha Sharir. Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications.

*SIAM J. Comput.*, 29:912–953, 1999.- [MO01]
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42.

*Internat. J. Comput. Geom. Appl.*, 11(5):573–582, 2001. Also in*SIGACT News*32(3):63-72 (2001), Issue 120.- [Var98]
K. Varadarajan. A divide and conquer algorithm for min-cost perfect matching in the plane. In

*Proc. 39th Annu. IEEE Sympos. Found. Comput. Sci.*, pages 320–329, 1998.- [Vai89]
P. M. Vaidya. Geometry helps in matching.

*SIAM J. Comput.*, 18:1201–1225, 1989.- [VA99]
K. R. Varadarajan and Pankaj K. Agarwal. Approximation algorithms for bipartite and non-bipartite matching in the plane. In

*Proc. 10th ACM-SIAM Sympos. Discrete Algorithms*, pages 805–814, 1999.