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!



Number of orthants intersected by a convex hull
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](https://mathoverflow.net/questions/38267/what-are-the-possible-numbers-of-regions-that-4-planes-can-divide-space)). In particular the $O(n^{k-1})$ bound is tight.


