ANear-Linear Time Algorithm for the Chamfer Distance

Further, the Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the quadratic dependence on n in the running time makes the naive approach intractable for large datasets. We overcome this bottleneck and present the first (1+")-approximate algorithm for estimating the Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time O ndlog(n)/"2 and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large highdimensional point clouds. We also give evidence that if the goal is to report a (1+")-approximate mapping from A to B (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.