An O (n 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 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_ (n^1. 5 poly (n) ) time.