next up previous
Next: Problem 7: k-sets Up: The Open Problems Project Previous: Problem 5: Euclidean Minimum

Problem 6: Minimum Euclidean Matching in 2D

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.
Uncertain, pending investigation.
Partial and Related Results
An algorithm that achieves the minimum and runs in nearly O(n2.5) time has long been available [Vai89]. This was improved to O(n1.5log5n) in [Var98]. Recently Arora showed how to achieve a (1 + ε)-approximation in n(log n)O(1/ε) time [Aro98], and this has been improved to O((n/ε3)log6n) 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(n2+ε) has been achieved [AES99], and a (1 + ε)-approximation can be found in O((n/ε)1.5log5n) time [VA99].

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


Sanjeev Arora.
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems.
J. Assoc. Comput. Mach., 45(5):753-782, 1998.

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.

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.

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.

P. M. Vaidya.
Geometry helps in matching.
SIAM J. Comput., 18:1201-1225, 1989.

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.

next up previous
Next: Problem 7: k-sets Up: The Open Problems Project Previous: Problem 5: Euclidean Minimum
The Open Problems Project - December 08, 2012