Deterministic, Near-Linear varepsilon-Approximation Algorithm for Geometric Bipartite Matching

Given point sets A and B in ℝd where A and B have equal size n for some constant dimension d and a parameter varepsilon>0, we present the first deterministic algorithm that computes, in n·(varepsilon-1 log n)O(d) time, a perfect matching between A and B whose cost is within a (1+varepsilon) factor of the optimal under any smashℓp-norm. Although a Monte-Carlo algorithm with a similar running time is proposed by Raghvendra and Agarwal [J. ACM 2020], the best-known deterministic varepsilon-approximation algorithm takes Omega(n3/2) time. Our algorithm constructs a (refinement of a) tree cover of ℝd, and we develop several new tools to apply a tree-cover based approach to compute an varepsilon-approximate perfect matching.