A deterministic coarse-net radius sweep for wide metric components
DefinitionStableMSR_Recovery_Supplement_CoarseSweepalgorithmsclustering
Coarse centers are separated at L/16 and cover their component. Radius-i regions are the fibers of the common ball membership tests on shifted representatives. The sweep uses a uniform grid between 3L/32 and L/8. The coarse packing cap and split budget depend only on the stability factor.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_ThresholdComponents
import Definitions.Def_StableMSR_Recovery_Supplement_Partitions
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
noncomputable def coarseCap (ε : ℝ) : ℕ := ⌈12*sigma/ε^2⌉₊
noncomputable def coarseBudget (ε : ℝ) : ℕ := ⌈(coarseCap ε : ℝ)*(1536/ε + 1)⌉₊
noncomputable def sweepRadius (L : ℝ) (n i : ℕ) : ℝ := 3*L/32 + (i:ℝ)*(L/(32*n))
def sameRow {n : ℕ} (p : Pack) (x y : Point n) : Prop :=
∃ w∈p, x∈rawBlock n w ∧ y∈rawBlock n w
abbrev SweepInput := Input × ℚ × ℚ × ℕ
/-- A fixed coarse net in each wide component; small-diameter fine components move whole.
Across the entire grid only the common testing radius varies. -/
def SweepSpec (I : RationalInput) (R L b : ℝ) (row : ℕ → Pack) : Prop :=
∃ (A : Cluster I.n → Cluster I.n) (f : Point I.n → Point I.n),
(∀ U ∈ wideComponents I.dist R L, A U ⊆ U ∧
(∀ z∈A U, ∀ z'∈A U, z≠z' → L/16 < I.dist z z') ∧
(∀ x∈U, ∃ z∈A U, I.dist z x ≤ L/16)) ∧
(∀ x, I.dist x (f x) ≤ 2*b) ∧
(∀ K∈components I.dist (2*b) Finset.univ, diameter I.dist K ≤ 2*b →
∀ x∈K, ∀ y∈K, f x = f y) ∧
∀ i<I.n, Represents I.n Finset.univ (row i) ∧ ∀ x y : Point I.n,
let U := component I.dist R Finset.univ x
sameRow (row i) x y ↔ y∈U ∧
(L < diameter I.dist U → ∀ z∈A U,
I.dist z (f x) ≤ sweepRadius L I.n i ↔ I.dist z (f y) ≤ sweepRadius L I.n i)
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Source
Refinement of the wide-component construction in S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Appendix A.2–A.3, Lemma A.1. The coarse net and uniformly spaced deterministic radius argument are an alternative with a larger parameter-dependent split bound. https://arxiv.org/abs/2611.03547