2
$\begingroup$

I'm trying to figure out the following problem:

Let $x_1,\ldots,x_k\in\mathbb{R}^n$ be some points for some $k<n$. Let $\mbox{conv} (x_1,\ldots,x_k)$ be their convex hull. I'm looking for a tight (possibly with an example) upper bound for the number of orthants that such convex hull can intersect with (depending on $n$ and $k$).

I've figured that as the convex hull of two points may intersect with up to $n$ orthants, by induction I can bound the number of intersections of $k$ points with different orthants to be $O(n^{k-1})$. I want to prove that this bound is tight or find a tighter one, hopefully with a concrete example.

Any ideas? Thanks!

$\endgroup$
6
$\begingroup$

Consider the $k-1$ dimensional simplex given by $\alpha_1+\alpha_2+\cdots \alpha_k=1, \alpha_i\geq 0$. The equations $e_i\cdot (\sum_{j=1}^k \alpha_j x_j)=0$ for $1\le i\le n$ describe $n$ hyperplanes that cut our simplex into several regions. Here $\cdot$ is the dot product and $e_i\in \mathbb R^n$ is the $i$-th coordinate vector.

It is easily seen that the number of orthants intersecting $\text{Conv}(x_1,x_2,\dots,x_k)$ is the same as the number of regions that our simplex was divided in. Therefore the question is actually equivalent to asking: "What is the highest number of regions that $\mathbb R^{k-1}$ can be divided into by $n$ hyperplanes?" The answer is given by $$1+n+\binom{n}{2}+\cdots+\binom{n}{k-1}$$ and can be proved by induction on both $k$ and $n$ (this fact is classical and has appeared on MO before, for example here). In particular the $O(n^{k-1})$ bound is tight.

$\endgroup$
4
  • $\begingroup$ So it is indeed $O(n^{k-1})$ and a polynomial in $n$. Given this, If we drop the requirement $n \gt k$ and observe that the answer is $2^n$ for $n \lt k$ , that determines the answer uniquely. $\endgroup$ – Aaron Meyerowitz Jan 1 '20 at 23:52
  • $\begingroup$ @AaronMeyerowitz yes! I prefer not to define it in separate cases, since the polynomial evaluated at $n<k$, does give the correct value $2^n$. Really the inductive proof makes everything clear, since it shows that the answer satisfies $a_{n,k}=a_{n-1, k}+a_{n-1,k-1}$ for all $n,k\geq 1$. $\endgroup$ – Gjergji Zaimi Jan 2 '20 at 0:00
  • $\begingroup$ It is true that the linked question has the stated result as one of the answers given. However it doesn’t answer the question asked. $\endgroup$ – Aaron Meyerowitz Jan 2 '20 at 0:02
  • $\begingroup$ Yes, the linked question is much harder and still doesn't have a satisfactory answer. $\endgroup$ – Gjergji Zaimi Jan 2 '20 at 0:18

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.