Size of the certified near-neighbour BSP
ProvedDetANN.HPIM.build_sizeapproximate-nearest-neighborcomputational-geometrydata-structures
Let , let with , , , and . Let , and build the certified near-neighbour BSP (definition DetANN_HPIMBuild) from the root box with fuel . Then the recursion does not starve, and
The bound depends only on , and , not on or on the spread of the points. Together with build_struct, it says that every leaf of is certified. Together with balance_spec, it makes every lookup cost node visits.
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMBuild
Formal statement
namespace DetANN.HPIM
/-- **Size of the certified near-neighbour BSP.** Let `m ≥ 1`, `n ≥ 1` points in `ℝ^m`, `r > 0`,
`δ ∈ (0, 1/2)`, `c = 1 + δ/4`. From the root box, with the fuel `bspFuel n m δ = ⌈n (2^12/ε)^{2m}⌉ + 1`
(`ε = δ/4`), the recursion of `build` does not starve, and the BSP has at most `2 · bspFuel n m δ`
nodes. The bound does not depend on `r` or on the spread of the points. -/
theorem build_size {m n : ℕ} (hm : 1 ≤ m) (hn : 0 < n) (pts : Fin n → Fin m → ℝ) (r δ : ℝ)
(hr : 0 < r) (hδ : 0 < δ) (hδ' : δ < 1 / 2) :
¬ Starves pts r (1 + δ / 4) (bspFuel n m δ) (rootLo hn pts r) (rootHi hn pts r) ∧
(build pts r (1 + δ / 4) (bspFuel n m δ) (rootLo hn pts r) (rootHi hn pts r)).paths.card ≤
2 * bspFuel n m δ := by sorry
end DetANN.HPIMSource
Original, written for the mission 'Deterministic Approximate Nearest Neighbors in High Dimensions' as part of a floor-free proof of DetANN.lemma_3_3 (Feng, Indyk, STOC 2027 submission, Lemma 3.3, p.7). The search tree follows Har-Peled, Indyk, Motwani, Approximate nearest neighbor: towards removing the curse of dimensionality, Theory of Computing 8 (2012), §2, made deterministic and floor-free.