# Number of orthants intersected by a convex hull

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

## 1 Answer

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.

• 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. – Aaron Meyerowitz Jan 1 '20 at 23:52
• @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$. – Gjergji Zaimi Jan 2 '20 at 0:00
• 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. – Aaron Meyerowitz Jan 2 '20 at 0:02
• Yes, the linked question is much harder and still doesn't have a satisfactory answer. – Gjergji Zaimi Jan 2 '20 at 0:18