Local distance-oracle regional trials for many large optimal clusters
OpenStableMSR.Recovery.RegionalBallDP.dense_local_region_menu_generatoralgorithmsclusteringdynamic-programmingformal-verification
Construct bounded real-distance RAM menus for the geometric branch of the stable-clustering algorithm. It suffices to exhibit a terminal whose incoming regional choices cover their newly owned points with distinct new centers and whose optimal local budgets extend from feasible predecessor counts. All these obligations concern individual menu entries or regions.
Preamble
import Definitions.Def_StableMSR_LocalBallTrials import Definitions.Def_StableMSR_RegionalBallDP open StableMSR.Recovery StableMSR.Recovery.Compiler StableMSR.Recovery.OracleQueries open StableMSR.Recovery.BallCoverCatalog StableMSR.Recovery.CartesianBallRows StableMSR.Recovery.FewBallRows open StableMSR.Recovery.RegionalBallDP open scoped Classical set_option autoImplicit false set_option maxHeartbeats 2200000 set_option maxRecDepth 12000
Formal statement
theorem StableMSR.Recovery.RegionalBallDP.dense_local_region_menu_generator : ∃a b : ℕ,0<a ∧ 0<b ∧ ∀e : ℚ,0<e → e<1 →
∃cmd : Cmd,∀(n k : ℕ) (d : Point n→Point n→ℝ),
1≤k → k<n → fewBound (e:ℝ)<k → IsMetricArray d → localSpec e a b cmd n k d := by
sorrySource
Exact Sum-of-Radii Clustering under Any Constant Stability, arXiv:2611.03547, Algorithm 1, equation (2), and Appendix A.4–A.6. Real-distance oracle implementation and witness reconstruction for the Prove2Me recovery mission.