# 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) –  Ross Millikan 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. –  Alex Ravsky 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$. –  Alex Ravsky 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$. –  Alex Ravsky Jun 4 '13 at 3:27
Even a bound $P(2,n)\ge\lceil n/2 \rceil$. –  Alex Ravsky 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? –  Milo Chen 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. :-( –  Alex Ravsky 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. –  Ross Millikan 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)$. –  Milo Chen Jun 4 '13 at 12:59