2025/12/18 by Goranci, Gramoz, Jiang, Shaofeng, Kiss, Peter +2
Computer Science · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2512.16639
openalex publication_date 2025/12/18 · openalex created_date 2025/12/21 · openalex updated_date 2026/07/28
We study the problem of computing Chamfer distance in the fully dynamic setting, where two set of points A, B ⊂ ℝ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) = ∑a ∈ 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 O(ε-d) update time and O(1/ε)-approximation in O(d nε2 ε-4) update time. We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.