Separation of convex sets
type: Item
instance of: scholarly article
title: Separation of convex sets
zbMATH Open document ID: 0806.52004
DOI: 10.1016/0166-218X(94)90030-2
published in: Discrete Applied Mathematics
publication date: 1994-07-31T00:00:00Z
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\).
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 52B99
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 612417
zbMATH Keywords: separation
zbMATH Keywords: closed discs
zbMATH Keywords: convex sets
author: Jurek Czyzowicz
author: E. Rivera-Campo
author: J. Urrutia
reviewed by: Rade Živaljević
MaRDI profile type: Publication
cites work: Cutting disjoint disks by straight lines
cites work: Separating convex sets in the plane
description: scientific article; zbMATH DE number 612417