pipette
ENEnglish

Fast Approximate Chamfer Distance via Lopsided Embeddings and Structured JL

Ying Feng, David P. Woodruff

Preprint

En palabras de los autores

For two -dimensional point sets of size , the Chamfer distance from to is defined as , where is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the norm for . For the general case , we utilize lopsided to embeddings with weak guarantees. We show that they are sufficient for preserving the Chamfer distance. In the high-dimensional regime, we use Fast Matrix Multiplication techniques to speed up the lopsided embeddings. These lead to total time. For the specific Euclidean case (), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous -specific Chamfer algorithm in . These achieve a runtime matching the recent state-of-the-art result of , improving upon the previous bound for . We also give additional results for the angular distance and upper and lower bounds in the streaming setting.

Resultado principalLimitación que admiten los autores

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Accepted at NeurIPS 2026