Proof of Lemma 4, p. 909 — an L_m ball of radius r lies in the axis-aligned hypercube of side 2r around its center
ProvedAryaANN.Search.ball_subset_cubeboxesminkowski-metricp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix an distance on with , a center and a real . Every point of the closed ball of radius about lies in the hypercube of side :
This reduces counting boxes that meet an ball to counting boxes that meet a cube, which is the shape used in the packing argument for Lemma 4.
Formalization Note The statement is given for the closed ball, which contains the open one.
Preamble
import Mathlib import Definitions.Def_AryaANN_Search_Setting
Formal statement
namespace AryaANN.Search
theorem ball_subset_cube {d : ℕ} (m : ℕ∞) (hm : 1 ≤ m) (c : Fin d → ℝ) (r : ℝ) :
∀ x : Fin d → ℝ, lmDist m c x ≤ r → ∀ i, |x i - c i| ≤ r := 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. 909, proof of Lemma 4, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.