A polynomial-bit maximal separated net on any listed subset
ProvedStableMSR.Recovery.Supplement.BinaryRecovery.Regional.binary_greedy_coarse_netalgorithmsclusteringcomputational-complexity
Scan an arbitrary listed subset, retaining a center only if no retained one lies within L/16. This computes a separated net covering the entire subset in polynomial bit time, including for inputs with repetitions.
Preamble
import Definitions.Def_QuantumMaxCutFiniteNumericRuntime import Definitions.Def_StableMSR_Recovery_Supplement_CoarseScan open StableMSR.Recovery StableMSR.Recovery.Supplement StableMSR.Recovery.Supplement.BinaryRecovery open StableMSR.Recovery.Supplement.BinaryRecovery.Regional open OAI.MetricKMedian.Binary.Automatic
Formal statement
theorem StableMSR.Recovery.Supplement.BinaryRecovery.Regional.binary_greedy_coarse_net :
Poly (fun z : Input × ℚ × Block => coarseScan z.1 z.2.1 z.2.2) ∧
∀ (I : RationalInput) (_ : I.Valid) (L : ℚ) (_ : 0≤L) (u : Block) (_ : ∀i∈u,i<I.n),
let U := rawBlock I.n u
let A := rawBlock I.n (coarseScan (fieldsOf I) L u)
A⊆U ∧ (∀z∈A, ∀w∈A, z≠w → (L:ℝ)/16 < I.dist z w) ∧
(∀x∈U, ∃z∈A, I.dist z x≤(L:ℝ)/16) := by
sorry
Source
Refinement of the wide-component construction in S. Ravichandran and L. Reyzin, Exact Sum-of-Radii Clustering under Any Constant Stability, Appendix A.2–A.3, Lemma A.1. The coarse net and uniformly spaced deterministic radius argument are an alternative with a larger parameter-dependent split bound. https://arxiv.org/abs/2611.03547