Centroid balancing of a BSP is correct and has logarithmic depth
ProvedDetANN.HPIM.balance_specapproximate-nearest-neighborcomputational-geometrydata-structures
Let be a BSP in that covers (definition DetANN_HPIMBSP), with nodes, and let be its balancing with fuel from the root. For every :
- if lies in the root box, then is the answer of some leaf of whose box contains ;
- visits at most nodes at .
The depth of itself can be linear in ; balancing makes the query cost logarithmic in its size. In the floor-free proof of DetANN.lemma_3_3, every near-neighbour lookup is a certified BSP whose leaves are correct answers, so this turns each lookup into a box decision tree with visits.
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMBSP
Formal statement
namespace DetANN.HPIM
/-- **Centroid balancing of a BSP.** Let `T` be a BSP in `ℝ^m` whose cuts cover their boxes, with
`|T|` nodes. The balanced box decision tree `balance T (|T| + 1) [] ∅` answers, at every `q` in the
root box, the answer of a leaf of `T` whose box contains `q`, and it visits at most
`5 ⌊log₂ |T|⌋ + 6` nodes at every `q`. -/
theorem balance_spec {m : ℕ} (T : BSP m) (hT : T.Covers) (q : Fin m → ℝ) :
(InBox T.box.1 T.box.2 q → ∃ p lo hi a, T.sub p = some (.leaf lo hi a) ∧ InBox lo hi q ∧
(balance T (T.paths.card + 1) [] ∅).eval q = a) ∧
(balance T (T.paths.card + 1) [] ∅).visits q ≤ 5 * Nat.log 2 T.paths.card + 6 := 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. The balancing is the standard centroid decomposition of a tree.