# Fully Dynamic Algorithms for Chamfer Distance

arXiv: https://arxiv.org/abs/2512.16639 · HTML: https://mlsanity.com/paper/2512.16639/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2025.

## Built on by (most cited first, 1 of 1)

- [Evaluating Mesh Reconstruction Methods for Crop Phenotyping](https://mlsanity.com/paper/2609.16926/) (2026)

## Abstract (arXiv)

We study the problem of computing Chamfer distance in the fully dynamic setting, where two set of points A, B subset ℝd, each of size up to n, dynamically evolve through point insertions or deletions and the goal is to efficiently maintain an approximation to distCH(A,B) = suma ∈ A minb ∈ B textrmdist(a,b), where textrmdist 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 ℓp norm for p ∈ 1,2 . Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, we obtain (1+ε)-approximation in tildeO(ε-d) update time and O(1/ε)-approximation in tildeO(d nε2 ε-4) update time. We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.