Fully Dynamic Algorithms for Chamfer Distance

We study the problem of computing Chamfer distance in the fully dynamic setting, where two set of points $A,B\subset {\mathbb{R}}^d$, each of size up to $n$, dynamically evolve through point insertions or deletions and the goal is to efficiently maintain an approximation to $dis{t}_{\mathrm{CH}}(A,B)={\sum }_{a\in A}{\min }_{b\in B}dist(a,b)$, where $dist$ is a distance measure. Chamfer distance is a widely used dissimilarity metric for point clouds, with many practical applications that require repeated evaluation on dynamically changing datasets, e.g., when used as a loss function in machine learning.

In this paper, we present the first dynamic algorithm for maintaining an approximation of the Chamfer distance under the ${\ell }_p$ norm for $p\in$ {$1,2$}. Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, we obtain $(1+ϵ)$-approximation in $\tilde{O}({ϵ}^{-d})$ update time and $O(1/ϵ)$-approximation in $\tilde{O}(d{n}^{{ϵ}^2}{ϵ}^{-4})$ update time.

We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.