2026-07-26T02:32:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19957 2024-06-06T06:21:13Z ddc:004 open_access

An O(n log n)-Time Approximation Scheme for Geometric Many-To-Many Matching Bandyapadhyay, Sayan Xue, Jie many-to-many matching geometric optimization approximation algorithms 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 L_p-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_p-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 ℝ¹ and ℝ², and the best known approximation scheme in ℝ² takes O_ε(n^{1.5} ⋅ poly(log n)) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sayan Bandyapadhyay and Jie Xue 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.12 urn:nbn:de:0030-drops-199577 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.12 eng https://creativecommons.org/licenses/by/4.0/legalcode