Near-Linear Time Algorithm for the Chamfer Distance

For any two point sets A, B ⊂ R d of size up to n, the Chamfer distance from A to B is defined as CH(A, B) = a∈A min b∈B d X (a, b), where d X is the underlying distance measure (e.g., the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward O dn 2 -time brute force algorithm. 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 nd log(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. 1 This is the definition adopted, e.g., in [AS03] . Some other papers, e.g., [FSG17], replace each distance term dX (a, b) with its square, e.g., instead of ∥a -b∥2 they use ∥a -b∥ 2 2 . In this paper we focus on the first definition, as it emphasizes the connection to Earth Mover Distance and its relaxed weighted version in [KSKW15, AM19]. Preprint. Under review.