Size of the HPIM tree
ProvedDetANN.HPIM.tree_pointsapproximate-nearest-neighborcomputational-geometrydata-structures
Let and let be distinct. Then
Here (definition DetANN_HPIMPreBlocks) is the total number of points over the HPIM tree of definition DetANN_HPIMTree, with the children of one node that have the same set counted once. The tree does not depend on .
This bounds the space of the preprocessing. Every node on points stores cells, so the total is .
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMPreBlocks import Definitions.Def_DetANN_HPIMLayout
Formal statement
namespace DetANN.HPIM
open PNormReg PNormRegLib
/-- **Size of the HPIM tree.** For distinct points, the total number of points over the tree, with the
children of one node that have the same set counted once, is at most `4 N (⌈log₂ N⌉ + 1)`. -/
theorem tree_points {m N : ℕ} (Y : Fin N → EuclideanSpace ℝ (Fin m)) (hY : Function.Injective Y) :
treePts Y (N + 1) Finset.univ ≤ 4 * N * (Nat.clog 2 N + 1) := 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 preprocessing program of DetANN.HPIM.hpim_preprocessing is assembled from these blocks. The machine is PNormReg (definition PNormReg_Machine) with the conventions of DetANN_DataStructure.