Separation of convex sets

Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Polytopes and polyhedra (52B99) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

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\).

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Separation of convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1329792)