<p>I have a set of <span class="math-container">$n$</span> convex polytopes of the form </p>

<p><span class="math-container">$$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$</span></p>

<p>where <span class="math-container">$C$</span> is a matrix and <span class="math-container">$\beta$</span> is a vector. I know that for each pair of polytopes <span class="math-container">$$(\mathcal{L}_k, \mathcal{L}_j)$$</span> there is a point of intersection other than the trivial solution <span class="math-container">$\beta = 0$</span>. Additionally, I know that <span class="math-container">$C_i$</span> is such that each entry of <span class="math-container">$\beta$</span> must be greater than or equal to zero. What I want to know is whether this implies that there exists a nontrivial point of intersection of all <span class="math-container">$n$</span> polytopes, or if there is some counterexample? </p>

<p>Thanks!</p>

CC BY-SA 4.0
2019-07-30T12:16:00.473Z
Counterexample (in 2D): Take the polytopes $x\ge 0$, $x\le 0$, $y\ge 0$ and $y\le 0$. Each pair intersects in at least a line, but the intersection of all of them is only $(0,0)$. Also, this is not really a research-level question, so may be more suited to cs.se.
Shaull
CC BY-SA 4.0
2019-07-30T12:34:49.457Z
Thanks! Added an edit to clarify a constraint on the problem I forgot to include.
Magdalen Dobson
CC BY-SA 4.0
2019-07-30T14:44:41.767Z
Still the answer is no, but you have to go to 3D: consider the three sides of a 3D simplex placed in the first octant -- these are three triangles that intersect in pairs, but have no common nontrivial intersection.
Shaull
CC BY-SA 4.0
2019-07-31T20:01:32.773Z
This feels similar to [Helly's theorem](https://en.wikipedia.org/wiki/Helly%27s_theorem)
Sasho Nikolov
<linear-algebra><linear-programming><polytope>
Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons
Magdalen Dobson
# Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons

(Asked by: username_0 on 2019-07-30)

I have a set of $n$ convex polytopes of the form

$$\mathcal{L\_i} = \{ \beta \mid C\_i \beta \leq 0 \}$$

where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\mathcal{L}\_k, \mathcal{L}\_j)$$ there is a point of intersection other than the trivial solution $\beta = 0$. Additionally, I know that $C\_i$ is such that each entry of $\beta$ must be greater than or equal to zero. What I want to know is whether this implies that there exists a nontrivial point of intersection of all $n$ polytopes, or if there is some counterexample?

Thanks!

**Tags:** linear-algebra, linear-programming, polytope
> **Comments:**
> **username_1**: Counterexample (in 2D): Take the polytopes $x\ge 0$, $x\le 0$, $y\ge 0$ and $y\le 0$. Each pair intersects in at least a line, but the intersection of all of them is only $(0,0)$. Also, this is not really a research-level question, so may be more suited to cs.se.  
> **username_0**: Thanks! Added an edit to clarify a constraint on the problem I forgot to include.  
> **username_1**: Still the answer is no, but you have to go to 3D: consider the three sides of a 3D simplex placed in the first octant -- these are three triangles that intersect in pairs, but have no common nontrivial intersection.  
> **username_2**: This feels similar to [Helly's theorem](https://en.wikipedia.org/wiki/Helly%27s_theorem)  

---

## 0 answers

