Constant local packing of L/16-separated coarse centers in a wide component
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.coarse_net_local_packingalgorithmsclusteringcomputational-complexity
Within distance 3L/16 of a point of a wide component, a family of L/16-separated coarse centers has size at most ceil(12σ/(γ−1)²). The L/32 fine-net neighborhoods are disjoint, each has at least L/(σR) points, and all lie in the L/4 neighborhood at the original point.
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_net_local_packing {n k : ℕ} (d : Point n→Point n→ℝ) (γ L : ℝ) (O : Partition n)
(hk : 1≤k) (kn : k<n) (hd : IsMetricArray d) (hg : 1<γ ∧ γ<2) (ho : Stable d k γ O)
(rp : 0<largestRadius d O)
(scale : sigma*largestRadius d O≤L ∧ L≤densityScale d O (γ-1))
(U : Cluster n) (hU : U∈wideComponents d (largestRadius d O) L)
(c : Point n) (hc : c∈U) (S : Cluster n) (hs : S⊆U)
(sep : ∀ z∈S, ∀ y∈S, z≠y → L/16 < d z y)
(near : ∀ z∈S, d c z≤3*L/16) : S.card≤coarseCap (γ-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