Regional priority balls, fallback balls, and their local contributions
DefinitionStableMSR_Recovery_Supplement_PriorityRegionsalgorithmsclustering
Offered large balls take precedence over deterministic threshold-radius balls at all input points. Each nonempty first-hit fiber contributes its actual residual set. The factor for a center consults only net vertices within 4R.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_CliqueFactors
import Definitions.Def_StableMSR_Recovery_Supplement_CoarseScan
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
abbrev Offer := Bool × BallCode
def regionPoints (z : RegionInput) : Block := (points z.1).filter (fun i => z.2.2.contains i)
def netKeys (z : RegionInput) : Block := coarseScan z.1 (32*z.2.1) (regionPoints z).reverse
def offerList (z : RegionInput) : List Offer :=
((ballCodes z.1).map (fun e => (true,e))) ++ ((points z.1).map (fun i => (false,(i,i))))
def offered (a : Input) (vs : Block) (R : ℚ) (s : Plan) (e : BallCode) : Bool :=
vs.any fun v => decide (scanDist a v e.1 ≤ 2*R) &&
(pickValue vs s v).any (fun p => decide (p.1=e.1) && decide (p.2=e.2))
def strikes (γ : ℚ) (z : RegionInput) (s : Plan) (o : Offer) (i : ℕ) : Bool :=
let a := z.1
let R := z.2.1
let e := o.2
if o.1 then offered a (netKeys z) R s e && decide (scanDist a e.1 e.2 ≤ R) &&
decide (scanDist a e.1 i ≤ scanDist a e.1 e.2)
else decide (scanDist a e.1 i ≤ (γ-1)*R/2)
def featureIds (z : RegionInput) : Block := List.range (offerList z).length
def featureScope (z : RegionInput) (j : ℕ) : Block :=
let c := ((offerList z)[j]?.getD (false,(0,0))).2.1
(netKeys z).filter (fun v => decide (scanDist z.1 c v ≤ 4*z.2.1))
def firstHit (γ : ℚ) (z : RegionInput) (s : Plan) (i : ℕ) : ℕ :=
(offerList z).findIdx (fun o => strikes γ z s o i)
def featureCell (γ : ℚ) (z : RegionInput) (j : ℕ) (s : Plan) : Block :=
(regionPoints z).filter (fun i => decide (firstHit γ z s i=j))
def featureOut (γ : ℚ) (z : RegionInput) (j : ℕ) (s : Plan) : Pack :=
let w := featureCell γ z j s
if w.isEmpty then [] else [w]
def priorityPack (γ : ℚ) (z : RegionInput) (s : Plan) : Pack :=
renderFactors (featureIds z) (featureOut γ z) s
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Proposition 4.2 and Appendices A.4 and A.6, https://arxiv.org/abs/2611.03547. The priority-ball construction is an alternative implementation of the regional optimization.