Matchings vs hitting sets among half-spaces in low dimensional euclidean spaces
classification
🧮 math.CO
cs.CGcs.DM
keywords
setsmathbbmathcalseparabledimensionaleithereuclideanlinearly
read the original abstract
Let $\mathcal{F}$ be any collection of linearly separable sets of a set $P$ of $n$ points either in $\mathbb{R}^2$, or in $\mathbb{R}^3$. We show that for every natural number $k$ either one can find $k$ pairwise disjoint sets in $\mathcal{F}$, or there are $O(k)$ points in $P$ that together hit all sets in $\mathcal{F}$. The proof is based on showing a similar result for families $\mathcal{F}$ of sets separable by pseudo-discs in $\mathbb{R}^2$. We complement these statements by showing that analogous result fails to hold for collections of linearly separable sets in $\mathbb{R}^4$ and higher dimensional euclidean spaces.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.