Repairing split clusters and normalizing overlapping regional covers
DefinitionStableMSR_Recovery_Supplement_RegionRepairalgorithmsclusteringdynamic-programming
Enumerate bounded lists of metric balls, remove their points from the old regions, add the balls as regions, and assign points to their first containing set to produce a disjoint partition.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_RegionalTables
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery.Regional
open BinaryVerifier
noncomputable def splitBlocks {n : ℕ} (O : Partition n) (ws : Pack) : Partition n := by
classical
exact O.filter (fun C => ¬∃ w∈ws, C⊆rawBlock n w)
def Seed (I : RationalInput) (O : Partition I.n) (γ : ℚ) (h : ℕ) (s : Scenario) : Prop :=
(s.1:ℝ)=largestRadius I.dist O ∧ Represents I.n Finset.univ s.2 ∧
2*(s.1:ℝ) ≤ densityScale I.dist O ((γ:ℝ)-1) ∧
(∀ w∈s.2, ∀ x∈rawBlock I.n w, ∀ y∈rawBlock I.n w, I.dist x y≤densityScale I.dist O ((γ:ℝ)-1)) ∧
(splitBlocks O s.2).card≤h
def ballRow (a : Input) (b : BallCode) : Block := (points a).filter (inside a b)
def residual (a : Input) (bs : List BallCode) (w : Block) : Block :=
w.filter (fun i => !(bs.any (fun b => inside a b i)))
def pieces (a : Input) (bs : List BallCode) (ws : Pack) : Pack :=
bs.map (ballRow a) ++ ws.map (residual a bs)
def owner (ps : Pack) (i : ℕ) := ps.findIdx (fun w => w.contains i)
def cell (a : Input) (ps : Pack) (j : ℕ) : Block :=
(points a).filter (fun i => decide (owner ps i=j))
def normalize (a : Input) (ps : Pack) : Pack :=
((List.range ps.length).filter (fun j => !(cell a ps j).isEmpty)).map (cell a ps)
def repairs (h : ℕ) (F : Input → List Scenario) (a : Input) : List Scenario :=
(F a).flatMap fun s => (tuples (ballCodes a) h).map fun bs => (s.1,normalize a (pieces a bs s.2))
end StableMSR.Recovery.Supplement.BinaryRecovery.Regional
Source
S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Section 4.1 equation (2), Proposition 4.2 and Appendices A.4–A.6. https://arxiv.org/abs/2611.03547