Bounded enumeration of large balls for binary exact clustering
DefinitionStableMSR_Recovery_Supplement_LargeBallSearchalgorithmsclusteringcomputational-complexity
Enumerate bounded lists of center–radius witnesses and an input maximum radius. Group guesses by ball membership, then group residual small clusters by a distance test. Compress the pointwise relation to consecutive labels.
Definition code
import Definitions.Def_StableMSR_Recovery_Supplement_CandidateSelection
import Definitions.Def_StableMSR_Recovery_Geometry
set_option autoImplicit false
namespace StableMSR.Recovery.Supplement.BinaryRecovery
open BinaryVerifier
abbrev BallCode := ℕ × ℕ
def ballCodes (a : Input) : List BallCode :=
(points a).flatMap fun c => (points a).map (fun x => (c,x))
def tuples {α : Type} (xs : List α) : ℕ → List (List α)
| 0 => [[]]
| h+1 => [] :: xs.flatMap (fun x => (tuples xs h).map (x :: ·))
def inside (a : Input) (b : BallCode) (i : ℕ) : Bool :=
decide (distAt a.1 a.2.2 b.1 i ≤ distAt a.1 a.2.2 b.1 b.2)
def grouped (a : Input) (bs : List BallCode) (t : ℚ) (i j : ℕ) : Bool :=
bs.any (fun b => inside a b i && inside a b j) ||
(!(bs.any (fun b => inside a b i)) && !(bs.any (fun b => inside a b j)) &&
decide (distAt a.1 a.2.2 i j ≤ t))
def fromRelation (ps : List ℕ) (r : ℕ → ℕ → Bool) : List ℕ :=
compact ps (ps.map fun i => (ps.filter (r i)).head?.getD 0)
def fewCandidates (γ : ℚ) (h : ℕ) (a : Input) : List (List ℕ) :=
(0 :: a.2.2).flatMap fun R => (tuples (ballCodes a) h).map fun bs =>
fromRelation (points a) (grouped a bs ((γ-1)*R/2))
def Appears (F : Input → List (List ℕ)) (I : RationalInput) (O : Partition I.n) : Prop :=
∃ l ∈ F (fieldsOf I), l.length=I.n ∧ labelsPartition I.n I.k l=O
end StableMSR.Recovery.Supplement.BinaryRecovery
Source
Ravichandran and Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Lemma 3.8, Section 4 Branch A and Branch B, Appendix A.5, and Proposition C.4. https://arxiv.org/abs/2611.03547