Chamfer distance breaks out of Euclidean: lopsided embeddings bring any ℓp approximation to near-linear time
Chamfer distance measures dissimilarity between two point sets, and efficient approximation had largely been limited to the Euclidean norm, leaving general ℓp norms open. This work reduces ℓp Chamfer distance to a low-dimensional ℓp instance using lopsided embeddings with weak guarantees, applies fast matrix multiplication to speed up the embedding in high dimensions, and obtains a near-linear-time approximation; for the Euclidean case it uses a Toeplitz-based fast Johnson-Lindenstrauss transform and matches the best known runtime.