Center-witness pairs repair every split optimal block in an arbitrary real-distance labeling
ProvedStableMSR.Recovery.WindowCSP.repair_split_signatures_with_distance_ballsalgorithmsclusteringformal-verificationgraph-theory
For each split optimal block, choose an optimal center and a farthest member. Stability makes the associated closed ball exactly that block. Encode all pairs in 2g base-n digits. The first covering ball is constant on each selected block. Every unselected optimal block keeps its original uniform color. A new color class is contained in either a selected block or a single old color class, so it retains the diameter bound.
Preamble
import Definitions.Def_StableMSR_ExplicitWindowScenes import Definitions.Def_StableMSR_WindowCSP open StableMSR.Recovery.WindowSweep StableMSR.Recovery.Supplement.BinaryRecovery.Regional open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open StableMSR.Recovery.Supplement StableMSR.Recovery.RegionalSeeds StableMSR.Recovery.WindowCSP open StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.FewBallRows open scoped Classical set_option autoImplicit false set_option maxHeartbeats 2400000 set_option maxRecDepth 12000
Formal statement
theorem StableMSR.Recovery.WindowCSP.repair_split_signatures_with_distance_balls (x : World) {α : Type} (key : Point x.n→α)
(γ D : ℝ) (hg : 1<γ) (hk : 1≤ x.k) (kn : x.k< x.n) (dm : IsMetricArray x.dist)
(O : Partition x.n) (hs : Stable x.dist x.k γ O)
(small : ∀p q,key p=key q → x.dist p q≤ D) (room : 2*largestRadius x.dist O≤ D) :
let g:=(splitBy O key).card
∃u< CartesianBallRows.rows x.n g,
(∀C∈O,∀p∈C,∀q∈C,repairKey x.dist key g u p=repairKey x.dist key g u q) ∧
∀p q,repairKey x.dist key g u p=repairKey x.dist key g u q → x.dist p q≤ D := by
sorrySource
Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Lemmas 3.3, 3.8, 3.9(iii), 4.4, Proposition 4.2, Algorithm 1, and Appendix A.4–A.6. Alternative pairwise formulation using bounded-overlap window traces in the mission’s real-distance model.