Research map / Learning theory and algorithms / Prediction and decision losses

Fully Dynamic Algorithms for Chamfer Distance

NeurIPS 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Metric and ordinal embedding · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives the first fully dynamic algorithm for approximating Chamfer distance under l1/l2 norms by importance sampling over a dynamic randomly-shifted quadtree, reducing to approximate nearest-neighbor queries.

Problem

Maintaining an approximation to the Chamfer distance between two dynamically changing point sets under point insertions and deletions, for l_p norms (p in {1,2}).

Approach

Maintain an implicit importance sampler over a dynamic randomly-shifted quadtree: each cell tracks how many A-points are matched in it, so sampling a cell by size times match count yields a point of A with probability roughly proportional to its Chamfer contribution; then estimate each sampled point's nearest-neighbor distance with an ANN oracle.

Key results

• Theory: (1+epsilon)-approximation in tilde-O(epsilon^{-d}) update time and O(1/epsilon)-approximation in tilde-O(d n^{epsilon^2} epsilon^{-4}) update time under l1.
• Experiments: the algorithm achieves less than 10% relative error using only hundreds of samples across four datasets, and runs magnitudes faster than the exact benchmark on larger datasets.
• Uniform sampling is competitive without outliers, but degrades significantly with injected outliers where the proposed method has a clear advantage.

Measured effects reported in the paper

Surprising findings

• Uniform sampling is competitive on real datasets without outliers and even slightly beats the proposed method on SIFT.
• Maintaining an alpha-approximate assignment requires Omega(n) recourse, so the estimate-only approach is needed.

Limitations

• Approximation for the l1 algorithm is (1+alpha+epsilon) with alpha tied to the NN oracle, so high-dimensional case only gives O(1/epsilon) approximation.
• Dynamic assignment maintenance requires Omega(n) recourse, so only estimates can be maintained efficiently.
• Main theorem holds with constant probability; boosting to high probability requires O(log n) parallel copies and a median, increasing query time.

Experimental setup

Datasets: Text Embedding ShapeNet Fashion-MNIST SIFT

Benchmarks: Text Embedding ShapeNet Fashion-MNIST SIFT

Metrics: relative error average running time per window update

Baselines: Benchmark (exact recomputation) Uniform sampling

Builds on: randomly-shifted quadtree static Chamfer distance importance sampling algorithm dynamic quadtree of Chen et al.

Closest papers by meaning

• Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond (NeurIPS 2025 · similarity 0.84)
• Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.83)
• Dynamic Facility Location in High Dimensional Euclidean Spaces (ICML 2024 · similarity 0.83)
• CMG-Net: Robust Normal Estimation for Point Clouds via Chamfer Normal Distance and Multi-Scale Geometry (AAAI 2024 · similarity 0.83)
• Learning Distances from Data with Normalizing Flows and Score Matching (ICML 2025 · similarity 0.83)
• Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.82)