{"ID":2827599,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.16639","arxiv_id":"2512.16639","title":"Fully Dynamic Algorithms for Chamfer Distance","abstract":"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 $\\mathrm{dist}_{\\mathrm{CH}}(A,B) = \\sum_{a \\in A} \\min_{b \\in B} \\textrm{dist}(a,b)$, where $\\textrm{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.","short_abstract":"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 $\\mathrm{dist}_{\\mathrm{CH}}(A,B) = \\sum_{a...","url_abs":"https://arxiv.org/abs/2512.16639","url_pdf":"https://arxiv.org/pdf/2512.16639v2","authors":"[\"Gramoz Goranci\",\"Shaofeng Jiang\",\"Peter Kiss\",\"Eva Szilagyi\",\"Qiaoyuan Yang\"]","published":"2025-12-18T15:11:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}