# A Near-Linear Time Algorithm for the Chamfer Distance

arXiv: https://arxiv.org/abs/2307.03043 · HTML: https://mlsanity.com/paper/2307.03043/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 29 references that are in the map.
- First posted on arXiv 6 Jul 2023.

## Builds on (most cited first, 8 of 8)

- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [ShapeNet: An Information-Rich 3D Model Repository](https://mlsanity.com/paper/1512.03012/) (2015)
- [A Point Set Generation Network for 3D Object Reconstruction from a Single Image](https://mlsanity.com/paper/1612.00603/) (2016)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Optimal Data-Dependent Hashing for Approximate Near Neighbors](https://mlsanity.com/paper/1501.01062/) (2015)
- [Transductive Zero-Shot Learning with Visual Structure Constraint](https://mlsanity.com/paper/1901.01570/) (2019)
- [LBS Autoencoder: Self-supervised Fitting of Articulated Meshes to Point Clouds](https://mlsanity.com/paper/1904.10037/) (2019)

## Built on by (most cited first, 5 of 5)

- [WordRobe: Text-Guided Generation of Textured 3D Garments](https://mlsanity.com/paper/2403.17541/) (2024)
- [LD-SDM: Language-Driven Hierarchical Species Distribution Modeling](https://mlsanity.com/paper/2312.08334/) (2023)
- [A Scalable Vector Graphics Latent Space](https://mlsanity.com/paper/2608.21893/) (2026)
- [Contextual Tokenization for Graph Inverted Indices](https://mlsanity.com/paper/2510.22479/) (2025)
- [The Observable Wasserstein Distance](https://mlsanity.com/paper/2605.09916/) (2026)

## Abstract (arXiv)

For any two point sets A,B subset ℝd of size up to n, the Chamfer distance from A to B is defined as CH(A,B)=suma ∈ A minb ∈ B dX(a,b), where dX is the underlying distance measure (e.g., the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward O(d n2)-time brute force algorithm. Further, the Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the quadratic dependence on n in the running time makes the naive approach intractable for large datasets. We overcome this bottleneck and present the first (1+ε)-approximate algorithm for estimating the Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time O(nd log (n)/varepsilon2) and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high-dimensional point clouds. We also give evidence that if the goal is to report a (1+varepsilon)-approximate mapping from A to B (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.