Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 (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)?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
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
1  
The paper appeared in Information Processing Letters; Volume 53, Issue 4, 24 February 1995, Pages 177–183, DOI: 10.1016/0020-0190(94)00186-3. The pdf-file from the website journal seems to be different from the one in your link, so hopefully there are no problems with the font in that file. In case you do not have access to the paper, feel free to email me and I can send you the pdf-file. –  Martin Sleziak Jun 5 '13 at 12:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.