# How many hyperplanes does it take to separate $n$ points in $\mathbb{R}^m$?

By 'separate', I mean that each point lies in its own little region/cell.

For instance, it takes a minimum of $P = 4$ lines to separate $n = 7$ points in $\mathbb{R}^2$ ($m=2$), assuming that no 3 points lie on a single line (i.e. are in general position): (Regular heptagon)

Now, in general, at least how many hyperplanes $P(m, n)$ does it take to separate $n$ points in $\mathbb{R}^m$ (assuming general position)?

• My intuition says the is an $\Bbb R^2$ problem-that in $\Bbb R^n$ the hardest problem will be if all the points are in a plane (or so close it doesn't matter) Jun 4 '13 at 3:08
• Conjecture. A maximal number of hyperplanes is needed when there exists a convex body containing all the points on its boundary. Jun 4 '13 at 3:16
• There is a trivial upper bound $P(m,n)\le n-1$. Morever, using an injective projection onto a hyperlance we should obtain an upper bound $P(m,n)\le P(m-1,n)$ for all $m\ge 2$. Jun 4 '13 at 3:18
• If $m=2$ and all points are vertices of a convex polyhon, then each separating line can interect the doundary of the polyhon in at most two points. This should yield the bound $P(2,n)\ge\lfloor n/2 \rfloor$. Jun 4 '13 at 3:27
• Even a bound $P(2,n)\ge\lceil n/2 \rceil$. Jun 4 '13 at 3:33

This question was considered by Ralph P. Boland and Jorge Urrutia in the paper “Separating Collections of Points in Euclidean Spaces”. I don't read this paper yet. As I understood, the authors showed that $$\lceil (n-1)/m\rceil\le P(m,n)\le \lceil(n-2^{\lceil\log m\rceil})/m\rceil+\lceil\log m\rceil,$$ and $P(2,n)=\lceil n/2\rceil$.
• Just to be clear, I presume that's $\log$ base 2? Jun 4 '13 at 10:33
• I don’t know, I hope this can be clarified from the paper. The pdf-file which I found has problems with the fonts, it even has no "$\le$" in the above bounds. :-( Jun 4 '13 at 10:41
• When I called it up it displays fine. I don't see why the dimension matters, as in higher dimension than $2$ I can always choose the points to lie in a plane. Maybe they prohibit that just like we prohibited all the points lying on one line. Jun 4 '13 at 12:42
• Yes, as in the notion of general position. Clearly, it requires more lines to separate collinear points. In particular, points in general position in $\mathbb{R^{m-1}}$ when viewed in $\mathbb{R^{m}}$ lie on a plane, which is no longer in general position (and is removed from consideration). Hence @AlexRavsky's deduction $P(m,n)≤P(m−1,n)$. Jun 4 '13 at 12:59