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!

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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