2
$\begingroup$

"Given $n$, find the minimal value of $k$ with the following property: Any $k$ (distinct) points in $\mathbb{R}^n$ can be partitioned into two disjoint subsets so that the intersection of the convex hulls of the two partitions is not empty."

A convex hull of a set is the "smallest" convex set which contains the set. A convex set $C$ is one in which $\forall x,y \in C$, $\lambda x + (1-\lambda)y \in C$ for $0 \leq \lambda \leq 1$.

For instance, in $\mathbb{R}$, suppose we have three points, $a,b,c$ with $a < b < c$. Then let $a$ and $c$ be in one partition and $b$ in the other. Clearly, the convex hull of $\{a,c\}$ is the line segment which indeed passes $b$.

In $\mathbb{R}^2$, I think $k=4$. We have four cases:

Case 1: All four points $a,b,c,d$ are collinear. Then the partitions can be $\{a,c\}$ and $\{b,d\}$ and their convex hulls clearly have non empty intersection.

Case 2: Three of the points are collinear, say $a,b,c,$ with $b$ between $a$ and $c$. Point $d$ is elsewhere. Then let the partitions again be $\{a,c\}$ and $\{b,d\}$.

Case 3: The four points form the vertices of a convex quadrilateral. Then let the convex hulls be the "diagonals".

Case 4: The four points form the vertices of a concave quadrilateral. Then three of the points form the vertices of a triangle and the fourth point would be inside that. The convex hull of $\{a,b,c\}$ is exactly that triangle.

I conjecture that $k=n+2$. I think that the convex hull of $n+1$ points in $\mathbb{R}^n$ is the $n$-simplex (I don't know if that's the right notation). We can always form a simplex with $n+1$ points and then have the last point be floating around. If that point is within the simplex (conjectured convex hull), then we are done. If it's outside it, we can sort of divide up the space based on the "faces" of our simplex.

For instance, in $\mathbb{R}^3$, we have five points. We can build a tetrahedron with four of the points. The tetrahedron will have four faces which can be extended to be four planes, dividing up the $\mathbb{R}^3$. Each plane cuts the space into two. So if our fifth point is on one side of the face, then there is an associated vertex of the tetrahedron on the other side. We can let that vertex and this fifth point be in a partition and the other three points in the other. Thus, we have a line segment passing through a triangle. If there's problems with the point being in the plane of one of the faces, I think we can still account for that case simply by forming a triangle and line segment.

But beyond $\mathbb{R}^n$, it isn't obvious to me how to prove or disprove the conjecture. I think the solution shouldn't require anything but rather elementary (not necessarily easy or simple, just techniques that a undergraduate or even high school student might recognize) methods. I don't actually know any algebraic geometry but I know that simplices and affine geometry has something to do with the problem; hence the tags.

Any ideas for solving this problem are welcome and appreciated.

$\endgroup$
  • $\begingroup$ The convex hull of $n$ affinely independent points in any Euclidean space is called an $n$-simplex (they are all affinely equivalent, i.e., for any two such there is an affine invertible map mapping one onto the other). And $n$ points $x_k$ are called affinely independent if $\sum a_kx_k=0$, with scalars $a_k$ satisfying $\sum a_k=0$, implies all $a_k=0$. $\endgroup$ – Harald Hanche-Olsen Nov 28 '14 at 20:26
  • $\begingroup$ I see. I don't actually know that much about those things but thank you. I was trying to use some rather elementary methods to solve this. $\endgroup$ – inkievoyd Nov 28 '14 at 20:30
  • 2
    $\begingroup$ That's okay. The geometric content is that if $n+1$ points in $\mathbb{R}^n$ are not affinely independent, then they all lie an $n-1$-dimensional hyperplane. $\endgroup$ – Harald Hanche-Olsen Nov 28 '14 at 20:32
  • $\begingroup$ Take a look at en.wikipedia.org/wiki/Radon%27s_theorem $\endgroup$ – Peter Wu Nov 30 '14 at 14:24
2
$\begingroup$

Your conjecture is correct. First, it is possible to place $n+1$ affinely independent points in $\mathbb{R}^n$, and these cannot be partitioned as suggested.

Second, given $n+2$ points $x_k\in\mathbb{R}^n$, they must be affinely in dependent, i.e., there are scalars $a_k$, not all zero, so that $$\sum_{k=1}^{n+2} a_kx_k=0,\quad\sum_{k=1}^{n+2}a_k=0.$$ Rewrite this as $$\sum_{a_k\ge0}a_kx_k=-\sum_{a_k<0}a_kx_k,$$ and divide both sides by $\sum_{a_k\ge0}a_k$ to get convex combinations on both sides.

$\endgroup$

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.