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 , each of size up to , dynamically evolve through point insertions or deletions and the goal is to efficiently maintain an approximation to , where 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 norm for . Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, we obtain -approximation in update time and -approximation in 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.
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 on10
- Hyperbolic Chamfer Distance for Point Cloud CompletionFangzhou Lin, Yun Yue, Songlin Hou, Xuechu Yu et al.ICCV 2023 · 53 citations
- The Structural Complexity of Matrix-Vector MultiplicationEmile Anand, Jan van den Brand, Rose McCartyNeurIPS 2025 · 12 citations
- Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious AdversariesMohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger et al.SODA 2023 · 11 citations
- Dynamic Correlation Clustering in Sublinear Update TimeVincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, Nikos ParotsidisICML 2024 · 7 citations
- Fully Dynamic Consistent k-Center ClusteringJakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram et al.SODA 2024 · 5 citations
Related papers
- Near-Linear Time Algorithm for the Chamfer DistanceAinesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal et al.NeurIPS 2023 · 9 citations
- Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update TimeGramoz Goranci, Peter Kiss, Neel Patel, Martin P. Seybold et al.ICML 2025
- Almost Optimal Fully Dynamic k-Center Clustering with RecourseSayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Silvio Lattanzi et al.ICML 2025
- Dynamic 3D Convex Hulls Revisited and ApplicationsHaitao WangSODA 2026
- On Adaptive Distance EstimationYeshwanth Cherapanamjeri, Jelani NelsonNeurIPS 2020 · 34 citations
