2024/02/24 by Bandyapadhyay, Sayan, Xue, Jie
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2402.15837
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 ℝd, 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 Lp-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 Lp-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 ℝ1 and ℝ2, and the best known approximation scheme in ℝ2 takes Oε(n1.5 ⋅ poly(log n)) time.