Lune

NeurIPS2025Top-tier venue

Fully Dynamic Algorithms for Chamfer Distance

Gramoz Goranci, Shaofeng H.-C. Jiang, Peter Kiss, Eva Szilagyi, Qiaoyuan Yang

Abstract

We study the problem of computing Chamfer distance in the fully dynamic setting, where two set of points A,B⊂RdA, B \subset \mathbb{R}^{d}, each of size up to nn, dynamically evolve through point insertions or deletions and the goal is to efficiently maintain an approximation to distCH(A,B)=∑a∈Amin⁡b∈Bdist(a,b)\mathrm{dist}_{\mathrm{CH}}(A,B) = \sum_{a \in A} \min_{b \in B} \textrm{dist}(a,b), where dist\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 ℓp\ell_p norm for p∈{1,2}p \in \{1,2 \}. Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, we obtain (1+ϵ)(1+\epsilon)-approximation in O~(ϵ−d)\tilde{O}(\epsilon^{-d}) update time and O(1/ϵ)O(1/\epsilon)-approximation in O~(dnϵ2ϵ−4)\tilde{O}(d n^{\epsilon^2} \epsilon^{-4}) update time. We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Dynamic Correlation Clustering in Sublinear Update Time cites Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
  • Fully Dynamic Consistent k-Center Clustering cites Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on10

  1. Hyperbolic Chamfer Distance for Point Cloud CompletionFangzhou Lin, Yun Yue, Songlin Hou, Xuechu Yu et al.ICCV 2023 · 53 citations
  2. The Structural Complexity of Matrix-Vector MultiplicationEmile Anand, Jan van den Brand, Rose McCartyNeurIPS 2025 · 12 citations
  3. Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious AdversariesMohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger et al.SODA 2023 · 11 citations
  4. Dynamic Correlation Clustering in Sublinear Update TimeVincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos ParotsidisICML 2024 · 7 citations
  5. Fully Dynamic Consistent k-Center ClusteringJakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram et al.SODA 2024 · 5 citations

Related papers

  1. Near-Linear Time Algorithm for the Chamfer DistanceAinesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal et al.NeurIPS 2023 · 9 citations
  2. Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update TimeGramoz Goranci, Peter Kiss, Neel Patel, Martin P. Seybold et al.ICML 2025
  3. Almost Optimal Fully Dynamic k-Center Clustering with RecourseSayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Silvio Lattanzi et al.ICML 2025
  4. Dynamic 3D Convex Hulls Revisited and ApplicationsHaitao WangSODA 2026
  5. On Adaptive Distance EstimationYeshwanth Cherapanamjeri, Jelani NelsonNeurIPS 2020 · 34 citations
Dusk over the sea between two cliffs drawn in fine vertical lines