Minimum Euclidean Matching in 2D

Definitions and mathematical statement

Let $S=\{p_1,\ldots,p_{2n}\}$ be distinct points in the Euclidean plane. A perfect matching is a partition of $S$ into $n$ unordered pairs. Its cost is \[ c(M)=\sum_{\{p_i,p_j\}\in M}\|p_i-p_j\|_2. \] The optimization task is to output a matching of minimum cost. Every pair of points is allowed; the main problem is not restricted to a prescribed bipartition. Ties may be resolved arbitrarily.

Determine the optimal asymptotic running time for this exact geometric optimization problem as $n$ grows. For the standard geometric formulation, work in a real-arithmetic model with exact arithmetic, square roots, and comparisons, and state whether an algorithm's bound is deterministic, expected, or amortized. A bit-complexity result on rational coordinates must instead account for coordinate lengths and exact comparisons of sums of distances.

The source also highlights the bipartite variant, with $n$ red and $n$ blue points and only red--blue pairs permitted. Bounds for that variant must be identified separately. Approximation schemes which return a matching within a factor $1+\varepsilon$ of the optimum do not determine the complexity of the exact task.

Short English statement

Determine how quickly the minimum-total-length perfect pairing of planar points can be computed exactly, and distinguish the bipartite version and approximation algorithms.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500006 (AMR-054-0006), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 6. Original source indexed by AMR-054-0006. https://topp.openproblem.net/p6.