A deterministic coarse-net sweep contains a bounded-split seed at a correct scale
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.stable_coarse_sweep_seedalgorithmsclusteringcomputational-complexity
For any coarse sweep with fixed center sets, a stable input at its true maximum radius and a good partition scale has a row of diameter at most the density scale splitting only a parameter-dependent constant number of optimal clusters. Small clusters have a common representative; each large split is charged to a nearby boundary interval.
Preamble
import Definitions.Def_StableMSR_Recovery_Supplement_CoarseSweep open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.stable_coarse_sweep_seed (γ : ℚ) (hg : 1<γ) (hu : γ<2) (I : RationalInput) (hv : I.Valid)
(O : Partition I.n) (ho : Stable I.dist I.k (γ:ℝ) O) (kn : I.k<I.n)
(R : ℚ) (hr : (R:ℝ)=largestRadius I.dist O) (rp : 0<(R:ℝ)) (L : ℝ)
(sl : sigma*(R:ℝ)≤L) (lu : L≤densityScale I.dist O ((γ:ℝ)-1))
(mass : largeMass I.dist O ((γ:ℝ)-1)/L < 8/((γ:ℝ)-1))
(row : ℕ→Pack) (run : SweepSpec I (R:ℝ) L (((γ:ℝ)-1)*R/4) row) :
∃ i<I.n, Seed I O γ (coarseBudget ((γ:ℝ)-1)) (R,row i) := by
sorry
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