For any two point sets $A,B \subset \mathbb{R}^d$ of size up to $n$, the
Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)=\sum_{a \in A}
\min_{b \in 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(d n^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 \emph{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+\epsilon)$-approximate
algorithm for estimating the Chamfer distance with a near-linear running time.
Specifically, our algorithm runs in time $O(nd \log (n)/\varepsilon^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 high-dimensional point clouds. We also give
evidence that if the goal is to \emph{report} a $(1+\varepsilon)$-approximate
mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic
time algorithm is unlikely to exist.

提出了一种使用近似算法以几乎线性的运行时间估算 Chamfer 距离的方法，适用于大规模高维数据集，为分析大规模高维点云开辟了新的途径。