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

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(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].

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

Bibliography

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.


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