Minimum Euclidean Matching in 2D

Let $n\in\mathbb{N}$ and let the input consist of $2n$ points in the plane. A matching pairs these points, and its cost is the sum of the Euclidean lengths of its edges. Determine the computational complexity of finding a matching whose cost is minimum.

Download

Abstract

For $2n$ points in the plane, the cost of a Euclidean matching is the total length of its edges. The open problem is to determine the computational complexity of finding a matching of minimum cost. An exact algorithm with running time $O(n^{1.5}\log^5 n)$ is reported.

Background and progress

The origin of the problem is uncertain. Let $n\in\mathbb{N}$ , so that the input contains $2n$ points. An exact algorithm with running time nearly $O(n^{2.5})$ was known [Vaidya, 1989]. This was improved to $O(n^{1.5}\log^5 n)$ [Varadarajan, 1998]. The source also reports approximation algorithms and results for the bipartite special case, but the complexity of computing an exact minimum-cost Euclidean matching remains open. The original problem appears in the Open Problems Project at https://topp.openproblem.net/p6.

Reference papers

Geometry helps in matchingP. M. VaidyaSIAM J. Comput. · 1989
A divide and conquer algorithm for min-cost perfect matching in the planeK. VaradarajanProc. 39th Annu. IEEE Sympos. Found. Comput. Sci. · 1998