The threshold graph and its median threshold
ProvedDetANN.HPIM.median_thresholdapproximate-nearest-neighborcomputational-geometrydata-structures
Let (definition DetANN_HPIMThreshold).
- If , two points in the same component of the threshold graph at are within .
- Every component has a representative.
- If some component at has at least points, there are at most representatives at .
- If and the points are distinct, let be the median threshold. Then some component at has at least points, , and for every every component at has at most points.
These are the facts about that the tree of Har-Peled, Indyk and Motwani (2012, §2) uses. Recursing into a component at the lower threshold, or into the representatives at , at least halves the point set, so the tree has depth . Item 1 bounds the diameters, and with them the length of the ladder of radii.
Preamble
import Mathlib import Definitions.Def_DetANN_HPIMThreshold
Formal statement
namespace DetANN.HPIM
open Classical in
/-- **The threshold graph and its median threshold.** For points `P_1, …, P_n ∈ ℝ^m` and `d ∈ ℝ`:
1. points in the same component of the threshold graph at `d ≥ 0` are within `(n − 1) d`;
2. every component has a representative (its least index);
3. if some component has at least `⌊n/2⌋ + 1` points, there are at most `⌈n/2⌉` representatives;
4. if `n ≥ 2` and the points are distinct, then at `d = medThreshold P` some component has at least
`⌊n/2⌋ + 1` points, `medThreshold P > 0`, and at every `d < medThreshold P` every component has at
most `⌊n/2⌋` points. -/
theorem median_threshold {m n : ℕ} (P : Fin n → EuclideanSpace ℝ (Fin m)) :
(∀ d : ℝ, 0 ≤ d → ∀ i j, thrReach P d i j → dist (P i) (P j) ≤ ((n : ℝ) - 1) * d) ∧
(∀ (d : ℝ) (i : Fin n), ∃ j, thrReach P d i j ∧ IsRep P d j) ∧
(∀ (d : ℝ) (i₀ : Fin n), n / 2 + 1 ≤ (Finset.univ.filter (thrReach P d i₀)).card →
(Finset.univ.filter (IsRep P d)).card ≤ (n + 1) / 2) ∧
(2 ≤ n → Function.Injective P →
(∃ i, n / 2 + 1 ≤ (Finset.univ.filter (thrReach P (medThreshold P) i)).card) ∧
0 < medThreshold P ∧
∀ d < medThreshold P, ∀ i, (Finset.univ.filter (thrReach P d i)).card ≤ n / 2) := 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.