pith. sign in

arxiv: 1507.02504 · v1 · pith:F6VBDNWYnew · submitted 2015-07-09 · 🧮 math.CO · cs.CG· cs.DM

Matchings vs hitting sets among half-spaces in low dimensional euclidean spaces

classification 🧮 math.CO cs.CGcs.DM
keywords setsmathbbmathcalseparabledimensionaleithereuclideanlinearly
0
0 comments X
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.