2
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Shaull
    Commented Jul 30, 2019 at 12:16
  • $\begingroup$ Thanks! Added an edit to clarify a constraint on the problem I forgot to include. $\endgroup$
    – Magdalen Dobson
    Commented Jul 30, 2019 at 12:34
  • 3
    $\begingroup$ 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. $\endgroup$
    – Shaull
    Commented Jul 30, 2019 at 14:44
  • 2
    $\begingroup$ This feels similar to Helly's theorem $\endgroup$
    – Sasho Nikolov
    Commented Jul 31, 2019 at 20:01

1 Answer 1

Reset to default
3
$\begingroup$

Your question is related to how to represent the geometric intersection objects. Pairwise comparisons can get a geometric intersection graph, however, the problem is that two objects are possibly not close to each other in this intersection graph, even originally their geometric distance is very short. So it is easy to find counterexamples for the specific question you asked: whether this implies that there exists a nontrivial point of intersection of all $n$ polytopes.

Given a geometric intersection graph, deciding which graph class it belongs to, the so-called recognition problem is not easy: Shaefer [1] proved that for intersection graphs of convex sets, the recognition problem is $\exists \mathbb{R}$-complete(It lies between NP and PSPACE).

[1] M. Schaefer. Complexity of some geometric and topological problems. In Proc. 17th Int. Symp. Graph Drawing (GD), pages 334–344, 2009.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.