2022/04/08 by Pankaj Agarwal, Hsien-Chih Chang, Agarwal, Pankaj K. +5 · 1 citation
Computer Science · Engineering · #3D Shape Modeling and Analysis #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2204.03875
openalex publication_date 2022/04/08 · openalex created_date 2022/04/15 · openalex updated_date 2026/07/28
Given point sets A and B in ℝd where A and B have equal size n for some constant dimension d and a parameter ε>0, we present the first deterministic algorithm that computes, in n⋅(ε-1 log n)O(d) time, a perfect matching between A and B whose cost is within a (1+ε) 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 ε-approximation algorithm takes Ω(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 ε-approximate perfect matching.