Separation of convex sets (Q1329792)

A hyperplane \(H\) separates a set \(A\) from a collection \({\mathcal K}\) of sets in \(\mathbb{R}^ d\) if \(A\) is contained in one of closed halfspaces determined by \(H\) and every member \(K \in {\mathcal K}\) is contained in the complementary closed halfspace. Let \(f_ d(n)\) be the largest integer so that for any collection \({\mathcal K}\) of closed discs in \(\mathbb{R}^ d\) with pairwise disjoint interiors, there exists a hyperplane separating one of the discs from at least \(f_ d(n)\) remaining discs from \({\mathcal K}\). The authors show that \(f_ 2(n) \geq (n - c)/2\) for a suitable constant \(c\). They extend this result in two ways by allowing general \(d\)-dimensional convex sets \(K\) with given ``degree of deformation'' \(e\) and show that essentially the same bound holds where the constant \(c = c(e,d)\) depends both on \(d\) and \(e\).