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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Jan 1, 2020 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
    Commented Jan 2, 2020 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
    Commented Jan 2, 2020 at 0:02
  • $\begingroup$ Yes, the linked question is much harder and still doesn't have a satisfactory answer. $\endgroup$
    – Gjergji Zaimi
    Commented Jan 2, 2020 at 0:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .