A common deterministic radius with few interval-charged cluster cuts
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.coarse_grid_averagingalgorithmsclusteringcomputational-complexity
If every bad cluster charges the grid radius to one of at most K intervals of length six times its radius, one of n deterministic radii has at most K(192 times the sum of radii divided by L, plus one) bad clusters. This is a finite double count including both endpoints of every 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.coarse_grid_averaging {α β : Type} [DecidableEq α] [DecidableEq β] (n K : ℕ) (hn : 0<n)
(L : ℝ) (hL : 0<L) (cs : Finset α) (hcs : cs.card≤n)
(rad : α→ℝ) (positive : ∀ C∈cs, 0≤rad C)
(zs : α→Finset β) (cap : ∀ C∈cs, (zs C).card≤K)
(center : α→β→ℝ) (bad : ℕ→Finset α)
(cover : ∀ i<n, ∀ C∈bad i, C∈cs ∧ ∃ z∈zs C,
center C z-3*rad C≤ sweepRadius L n i ∧ sweepRadius L n i≤center C z+3*rad C) :
∃ i<n, ((bad i).card:ℝ) ≤ (K:ℝ)*(192*(∑ C∈cs, rad C)/L+1) := 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