2026-07-23T04:53:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23453 2025-10-02T12:55:34Z ddc:004 open_access

Even Faster Algorithm for the Chamfer Distance Feng, Ying Indyk, Piotr Chamfer distance For two d-dimensional point sets A,B of size up to n, the Chamfer distance from A to B is defined as CH(A,B) = ∑_{a ∈ A} min_{b ∈ B} ‖a-b‖. The Chamfer distance is a widely used measure for quantifying dissimilarity between sets of points, used in many machine learning and computer vision applications. A recent work of Bakshi et al, NeuriPS'23, gave the first near-linear time (1+ε)-approximate algorithm, with a running time of 𝒪(nd log (n)/ε²). In this paper we improve the running time further, to 𝒪(nd(log log n+log1/(ε))/ε²)). When ε is a constant, this reduces the gap between the upper bound and the trivial Ω(dn) lower bound significantly, from 𝒪(log n) to 𝒪(log log n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ying Feng and Piotr Indyk 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.76 urn:nbn:de:0030-drops-234531 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.76 eng https://creativecommons.org/licenses/by/4.0/legalcode