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

  • $\begingroup$ 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) $\endgroup$ Jun 4 '13 at 3:08
  • $\begingroup$ Conjecture. A maximal number of hyperplanes is needed when there exists a convex body containing all the points on its boundary. $\endgroup$ Jun 4 '13 at 3:16
  • $\begingroup$ 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$. $\endgroup$ Jun 4 '13 at 3:18
  • $\begingroup$ 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$. $\endgroup$ Jun 4 '13 at 3:27
  • $\begingroup$ Even a bound $P(2,n)\ge\lceil n/2 \rceil$. $\endgroup$ 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$.

  • $\begingroup$ Just to be clear, I presume that's $\log$ base 2? $\endgroup$
    – mchen
    Jun 4 '13 at 10:33
  • $\begingroup$ 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. :-( $\endgroup$ Jun 4 '13 at 10:41
  • $\begingroup$ 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. $\endgroup$ Jun 4 '13 at 12:42
  • $\begingroup$ 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)$. $\endgroup$
    – mchen
    Jun 4 '13 at 12:59
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 5 '13 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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