An O(n log n)-Time Approximation Scheme for Geometric Many-to-Many Matching

Geometric matching is an important topic in computational geometry and has been extensively studied over decades. In this paper, we study a geometric-matching problem, known as geometric many-to-many matching. In this problem, the input is a set S of n colored points in Rᵈ, which implicitly defines a graph $G = (S,E(S))$ where E(S) = \(p,q): p,q ∈ S have different colors\, and the goal is to compute a minimum-cost subset E^* ⊆ E(S) of edges that cover all points in S. Here the cost of E^* is the sum of the costs of all edges in E^*, where the cost of a single edge e is the Euclidean distance (or more generally, the Lₚ-distance) between the two endpoints of e. Our main result is a (1+ε)-approximation algorithm with an optimal running time O_ε(n log n) for geometric many-to-many matching in any fixed dimension, which works under any Lₚ-norm. This is the first near-linear approximation scheme for the problem in any d ≥ 2. Prior to this work, only the bipartite case of geometric many-to-many matching was considered in R¹ and R², and the best known approximation scheme in R² takes O_ε(n1.5 · poly(log n)) time.