pith. sign in

arxiv: 2605.25280 · v2 · pith:OBAZHKY3new · submitted 2026-05-24 · 💻 cs.DS · cs.CC· cs.CG

Approximate Algorithms for Chamfer Distance Under Translation

Gil Halevi , Daniel Zhang , Jason Zhang This is my paper

Pith reviewed 2026-06-29 23:19 UTC · model grok-4.3

classification 💻 cs.DS cs.CCcs.CG
keywords Chamfer distanceunder translationapproximation algorithmsfine-grained complexitypoint setsdecision versioncomputational geometry
0
0 comments X

The pith

New algorithms approximate Chamfer distance under translation to (1+ε) or (2+ε) factors in near-quadratic time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines Chamfer distance under translation as the minimum Chamfer distance between two point sets after translating one set by any vector t. It supplies four algorithms: an exact quadratic-time solution in one dimension, a near-quadratic (2+ε)-approximation in higher dimensions, a (1+ε)-approximation in O(m n² ε^{-(d+1)}) time, and a near-quadratic (1+ε)-approximation for the decision version when points in the second set are separated. A sympathetic reader cares because Chamfer distance substitutes for Earth Mover's distance in vision and retrieval tasks, and translations often represent irrelevant shifts such as time or position. The work also examines fine-grained complexity to understand limits on faster exact solutions.

Core claim

Chamfer distance under translation, defined as min over t in R^d of CD(A+t, B), admits an exact quadratic-time algorithm in one dimension, a near-quadratic (2+ε)-approximation algorithm in higher dimensions, a (1+ε)-approximation algorithm with running time O(m n² ε^{-(d+1)}), and a near-quadratic (1+ε)-approximation algorithm for the decision version given a separation assumption on B. The paper additionally explores the fine-grained complexity of the problem.

What carries the argument

Chamfer distance under translation (CDuT), the minimum over translations t of the sum over a in A of the minimum distance from a+t to any point in B.

If this is right

  • Dissimilarity between point sets can be measured efficiently even when one set is shifted by an unknown amount.
  • The decision version of the problem becomes tractable in near-quadratic time when points satisfy the separation condition.
  • Exact solutions exist in quadratic time for the one-dimensional case.
  • Fine-grained complexity results indicate barriers to subquadratic exact algorithms in higher dimensions.
  • The (1+ε) approximation in O(m n² ε^{-(d+1)}) time applies without separation assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar approximation techniques could extend to translation-invariant versions of other set distances such as Hausdorff distance.
  • The separation assumption might be bypassed in practice by first clustering or sparsifying the point set B.
  • Fine-grained complexity connections may link CDuT to other geometric problems like bipartite matching under translation.
  • The algorithms enable alignment of point clouds where only relative shape matters after removing global shifts.

Load-bearing premise

The points in set B are sufficiently separated for the near-quadratic (1+ε) decision algorithm to achieve its claimed runtime and approximation guarantee.

What would settle it

A concrete collection of point sets B with insufficient separation where the near-quadratic (1+ε) decision algorithm either exceeds its stated runtime bound or fails to return a (1+ε)-approximate answer.

Figures

Figures reproduced from arXiv: 2605.25280 by Daniel Zhang, Gil Halevi, Jason Zhang.

Figure 1
Figure 1. Figure 1: The (1 + ε)-ChamferDistanceUnderTranslation Algorithm during preprocessing we build a multi-scale LSH data structure on B in space O(n 1+ 1 2c2−1 log(n)) and time O(n 1+ 1 2c2−1 log(n)) for giving c-approximations to nearest neighbor queries in time O(n 1 2c2−1 log(n)d). For each translation t, for each point ai ∈ A, we query the data structure with vector ai +t and store the approximate distance to its ne… view at source ↗
read the original abstract

Given two sets of points A and B, $|A| = m$, $|B| = n$, the Chamfer distance from $A$ to $B$ is defined as $\operatorname{CD}(A,B) = \sum_{a\in A} \min_{b\in B} d(a,b)$, where $d$ is a distance metric. Chamfer distance is a popular measure of dissimilarity between two sets of points that has seen increasing usage in computer vision and information retrieval as a substitute for the more computationally demanding Earth Mover's distance. We propose a new problem, Chamfer distance under translation, defined as $\operatorname{CDuT}(A,B) :=\min_{t\in \mathbb{R}^d} \operatorname{CD}(A+t,B)$, where $A+t$ denotes the translation of every point in $A$ by $t$. Chamfer distance under translation is valuable in cases where translations capture aspects of the data unlikely to be relevant for dissimilarity, such as temporal, spatial, or other semantic information. For Chamfer distance under translation, we provide four algorithms: (1) an exact quadratic time algorithm in one dimension, (2) a near quadratic time ($2+\varepsilon$)-approximation algorithm in higher dimensions, (3) a $(1+\varepsilon)$-approximation algorithm with running time $\mathcal{O}(mn^2\varepsilon^{-(d+1)})$, and (4) a near-quadratic time $(1+\varepsilon)$-approximation algorithm for answering the decision version of $\operatorname{CDuT}$ given a separation assumption on $B$. We additionally explore the fine-grained complexity of $\operatorname{CDuT}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper introduces Chamfer distance under translation (CDuT) as min over translations t of CD(A+t, B). It gives four algorithms: (1) exact quadratic-time in 1D, (2) near-quadratic (2+ε)-approximation in d>1, (3) (1+ε)-approximation in O(m n² ε^{-(d+1)}) time, (4) near-quadratic (1+ε)-approximation decision algorithm under an explicit separation assumption on B, plus fine-grained complexity results.

Significance. If correct, the algorithms supply practical near-quadratic approximations for a dissimilarity measure used in computer vision and information retrieval. The explicit statement of the separation assumption for algorithm (4) and the fine-grained complexity exploration are strengths that aid usability and theoretical context.

major comments (1)
  1. [Abstract] Abstract (algorithm 4): the near-quadratic (1+ε) decision algorithm is stated to require a separation assumption on B. This assumption is load-bearing for the claimed runtime; the manuscript should clarify whether the assumption can be removed while retaining the bound or provide a reduction that handles the general case.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and helpful suggestion regarding the presentation of algorithm (4). We will revise the abstract and add a clarifying remark in the main text to address the load-bearing nature of the separation assumption.

read point-by-point responses

  1. Referee: [Abstract] Abstract (algorithm 4): the near-quadratic (1+ε) decision algorithm is stated to require a separation assumption on B. This assumption is load-bearing for the claimed runtime; the manuscript should clarify whether the assumption can be removed while retaining the bound or provide a reduction that handles the general case.

    Authors: We agree that the separation assumption on B is essential for obtaining the near-quadratic runtime in the (1+ε)-approximation decision algorithm. The assumption is used to ensure that candidate translations can be efficiently enumerated without encountering dense clusters that would degrade the runtime. At present, we do not know of a way to remove the assumption while preserving the near-quadratic bound, nor do we have a reduction that extends the result to the fully general case. We will revise the abstract to explicitly note that the near-quadratic runtime holds under the stated separation assumption on B, and we will add a short discussion in Section 4 explaining why the assumption is required for the current analysis. revision: yes

Circularity Check

0 steps flagged

No circularity; direct algorithmic constructions with explicit preconditions

full rationale

The paper defines CDuT and presents four explicit algorithms with stated runtimes and approximation guarantees. None of the claims reduce by construction to fitted parameters, self-definitions, or self-citation chains. The separation assumption on B is an explicit precondition stated in the abstract for algorithm (4); it does not create circularity because the algorithm is presented as conditional on that assumption rather than claiming to derive or remove it. No equations equate a 'prediction' to its own input, and no uniqueness theorems or ansatzes are smuggled via self-citation. The derivation chain consists of standard algorithmic design (exact 1D solution, approximation schemes) that stands independently of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces a new optimization problem but relies only on standard assumptions from computational geometry; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (1)
  • standard math Standard nearest-neighbor queries and distance computations in Euclidean space are efficient under the metric d.
    All listed algorithms presuppose the ability to compute min distances; this is a background assumption of the field.

pith-pipeline@v0.9.1-grok · 5833 in / 1233 out tokens · 32443 ms · 2026-06-29T23:19:12.072987+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Multi-Vector Embeddings are Provably More Expressive than Single Vector Embeddings

    cs.DS 2026-06 unverdicted novelty 8.0

    Proves that for bounded n, there exist MV embeddings with m vectors each whose Chamfer matrix requires single-vector dimension D = (ε² m)^Ω(1/ε) to approximate within ε, separating MV from SV expressiveness.

Reference graph

Works this paper leans on

10 extracted references · 8 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    doi: 10.1145/1824777.1824791

    ISSN 1549-6325. doi: 10.1145/1824777.1824791. URLhttps://doi.org/10.1145/1824777.1824791. Alexandr Andoni and Ilya P. Razenshteyn. Optimal data-dependent hashing for approximate near neighbors.CoRR, abs/1501.01062,

    work page doi:10.1145/1824777.1824791

  2. [2]

    Optimal Data-Dependent Hashing for Approximate Near Neighbors

    URLhttp://arxiv.org/abs/1501.01062. Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, and Erik Waingarten. A near-linear time algorithm for the chamfer distance,

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    Karl Bringmann and André Nusser

    URLhttps://arxiv.org/abs/2307.03043. Karl Bringmann and André Nusser. Translating hausdorff is hard: Fine-grained lower bounds for hausdorff distance under translation.CoRR, abs/2101.07696,

    work page arXiv

  4. [4]

    Karl Bringmann, Marvin Künnemann, and André Nusser

    URLhttps://arxiv.org/ abs/2101.07696. Karl Bringmann, Marvin Künnemann, and André Nusser. Discrete fréchet distance under transla- tion: Conditional hardness and an improved algorithm.ACM Trans. Algorithms, 17(3), July

    work page arXiv

  5. [5]

    doi: 10.1145/3460656

    ISSN 1549-6325. doi: 10.1145/3460656. URLhttps://doi.org/10.1145/3460656. Karl Bringmann, Frank Staals, Karol W˛ egrzycki, and Geert van Wordragen. Fine-grained com- plexity of earth mover’s distance under translation.Journal of Computational Geometry, 16,

    work page doi:10.1145/3460656

  6. [6]

    Geometric Median in Nearly Linear Time

    doi: 10.20382/JOCG.V16I2A10. URLhttps://jocg.org/index.php/jocg/ article/view/5656. Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time.CoRR, abs/1606.05225,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.20382/jocg.v16i2a10

  7. [7]

    Geometric Median in Nearly Linear Time

    URLhttp://arxiv.org/abs/ 1606.05225. Omrit Filtser and Matthew Katz. Algorithms for the discrete fréchet distance under translation. Journal of Computational Geometry, 11(1):156–175, Jun

    work page internal anchor Pith review Pith/arXiv arXiv

  8. [8]

    URLhttps://jocg.org/index.php/jocg/article/view/3097

    doi: 10.20382/jocg.v11i1a7. URLhttps://jocg.org/index.php/jocg/article/view/3097. Piotr Indyk. A near linear time constant factor approximation for euclidean bichromatic matching (cost). InProceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’07, page 39–42, USA,

    work page doi:10.20382/jocg.v11i1a7

  9. [9]

    There areO(mn)possible alignments in each dimension, which results inO(m dnd)possible candidates

    Therefore for any translation in the other dimensions, this dimension must be aligned, and therefore all dimensions must be aligned. There areO(mn)possible alignments in each dimension, which results inO(m dnd)possible candidates. Computing the Chamfer distance of each candidate takesO(mn)naively, granting a O(md+1nd+1)algorithm. The technique of shaving ...

    2015

  10. [10]

    Each run of that algorithm gives an estimate in the range [CD(A+t, B),( 1+ ε 16 1− ε 16 )CD(A + t,B)]⊂[CD(A+t, B),(1 + ε 4)CD(A + t,B)]with probabil- ity≥0.99

    (setting theεin that algorithm to ourε/16 =O(ε))ltimes and then take their median, scaled by 1 1− ε 16 so that it is not an underestimate. Each run of that algorithm gives an estimate in the range [CD(A+t, B),( 1+ ε 16 1− ε 16 )CD(A + t,B)]⊂[CD(A+t, B),(1 + ε 4)CD(A + t,B)]with probabil- ity≥0.99. We setlso that the probability that a given median estimat...

    2007