Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5, p. 911 — the nearest neighbor search on a BBD-tree visits at most ⌈1 + 6d/ε⌉^d leaf cells, for any Minkowski metric

Proved
AryaANN.Search.lemma_5

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximationbbd-treenearest-neighborp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1packing

Let TTT be a valid BBD-tree whose root cell is a box CCC with no inner box, fix an LmL_mLm​ distance on Rd\mathbb R^dRd with 1≤m≤∞1\le m\le\infty1≤m≤∞ ("any Minkowski metric"), an approximation parameter ε>0\varepsilon>0ε>0 and a query point q∈Rdq\in\mathbb R^dq∈Rd. Let E=((c0,p0),(c1,p1),… )E=((c_0,p_0),(c_1,p_1),\dots)E=((c0​,p0​),(c1​,p1​),…) be an enumeration of the leaf cells of TTT such that

  1. every leaf cell occurs exactly once;
  2. the cells occur in nondecreasing order of distance from qqq (ties in any order);
  3. the data point pjp_jpj​ associated with cjc_jcj​ lies in the outer box of cjc_jcj​.

The search processes c0,c1,…c_0,c_1,\dotsc0​,c1​,… in turn, keeping the closest point ppp seen so far, and terminates at the first cell whose distance from qqq exceeds dist⁡m(q,p)/(1+ε)\operatorname{dist}_m(q,p)/(1+\varepsilon)distm​(q,p)/(1+ε). The number NNN of cells visited up until termination, that is, the cells preceding the terminating cell, satisfies

N≤⌈1+6dε⌉d.N\le\Big\lceil 1+\frac{6d}{\varepsilon}\Big\rceil^d.N≤⌈1+ε6d​⌉d.

The bound does not depend on the number of data points. Multiplied by the O(log⁡n)O(\log n)O(logn) cost of enumerating each cell, it gives the query time of Theorem 1(i).

Formalization Note The paper's Cd,εC_{d,\varepsilon}Cd,ε​ is a name for the number of visited cells; the formal conclusion is the explicit bound. A cell is processed (its point compared) before its own termination test, and NNN counts the cells processed before the one whose test fires, or all of them if none fires. This is the count bounded in the paper's proof, where rrr is the distance to "the last leaf cell that did not cause the algorithm to terminate" (p. 912). The printed statement says "the number of leaf cells visited"; if the firing cell is also counted, a valid one-dimensional tree with ε=6\varepsilon=6ε=6 needs three processed cells against the bound 222, so the formal statement follows the proof's count (the discrepancy is recorded in HARD.md). The enumeration is a permutation of the leaf cells sorted by distance, the abstract output of property (e); the associated point lies in the cell's outer box, as in properties (a)–(b). The tree is any tree satisfying the §2.1 invariants, with any box as root. Theorem 1's O(⋅)O(\cdot)O(⋅) time and space claims are not formalized.

Preamble
import Mathlib
import Definitions.Def_AryaANN_Search_Setting
Formal statement
namespace AryaANN.Search

/-- Lemma 5 (p. 911): the number `N` of leaf cells the search visits up until termination is at
most `⌈1 + 6d/ε⌉^d`. As in the proof (p. 912), `N` counts the cells that did not cause termination;
the cell whose test fires is not counted (counting it, the printed bound can be exceeded by one). -/
theorem lemma_5 {d : ℕ} (m : ℕ∞) (hm : 1 ≤ m) (C : Rect d) (T : BBDTree d)
    (hT : Valid ⟨C, none⟩ T) (ε : ℝ) (hε : 0 < ε) (q : Fin d → ℝ)
    (E : List (Cell d × (Fin d → ℝ)))
    (hperm : (E.map Prod.fst).Perm (leaves ⟨C, none⟩ T))
    (hpt : ∀ e ∈ E, e.2 ∈ e.1.outer.toSet)
    (hsorted : E.Pairwise (fun a b => cellDist m q a.1 ≤ cellDist m q b.1))
    (N : ℕ) (hN : IsVisitCount m ε q E N) :
    N ≤ ⌈1 + 6 * (d : ℝ) / ε⌉₊ ^ d := by sorry

end AryaANN.Search
Source
Arya et al., An optimal algorithm for approximate nearest neighbor searching in fixed dimensions, J. ACM 45 (1998), p. 911, Lemma 5 (with the search of §4, p. 911, and its proof, p. 912)
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me