<p>Consider the following two system of linear (in)eqaulities:</p>

<p>$S = Ax \leq b;\; Cx = e$</p>

<p>$T = Dx \leq d;\; Gx = g$</p>

<p>How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the linear system $T$. </p>

CC BY-SA 3.0
2015-10-14T08:51:22.327Z
http://mathoverflow.net/q/219057/35417 "Testing if a point is inside a convex polytope formed by halfspaces in n-dimension" is different but related
Zsbán Ambrus
CC BY-SA 3.0
2015-10-14T12:07:41.480Z
Your question has been answered here: http://cstheory.stackexchange.com/questions/32587/checking-equivalence-of-two-polytopes/32589#32589
Christoph Haase
CC BY-SA 3.0
2015-10-14T15:30:11.280Z
@ChristophHaase, did you find a source that this problem is $\Pi_2^P$-hard?
usul
CC BY-SA 3.0
2015-10-14T16:10:45.803Z
I do not see the connection of the proposed source to my problem. Could you please clarify it more?
Star
CC BY-SA 3.0
2015-10-19T09:39:40.000Z
@ChristophHaase, did you find a source that this problem is ΠP2-hard?
Star
CC BY-SA 3.0
2015-10-20T21:32:00.560Z
You are asking for an algorithm to check whether a polytope $T$ is included (for usual set inclusion) in another polytope $S$.
It does not look like a research-level question to me. Or you need to be more specific: are you rather interested in the complexity, as your comment suggests?
Boson
<ds.algorithms><linear-algebra><linear-programming><computational-geometry>
Inclusion of polytopes
Star
# Inclusion of polytopes

(Asked by: username_0 on 2015-10-13)

Consider the following two system of linear (in)eqaulities:

$S = Ax \leq b;\; Cx = e$

$T = Dx \leq d;\; Gx = g$

How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the linear system $T$.

**Tags:** ds.algorithms, linear-algebra, linear-programming, computational-geometry
> **Comments:**
> **username_1**: http://mathoverflow.net/q/219057/35417 "Testing if a point is inside a convex polytope formed by halfspaces in n-dimension" is different but related  
> **username_2**: Your question has been answered here: http://cstheory.stackexchange.com/questions/32587/checking-equivalence-of-two-polytopes/32589#32589  
> **username_3**: @ChristophHaase, did you find a source that this problem is $\Pi_2^P$-hard?  
> **username_0**: I do not see the connection of the proposed source to my problem. Could you please clarify it more?  
> **username_0**: @ChristophHaase, did you find a source that this problem is ΠP2-hard?  
> **username_4**: You are asking for an algorithm to check whether a polytope $T$ is included (for usual set inclusion) in another polytope $S$. It does not look like a research-level question to me. Or you need to be more specific: are you rather interested in the complexity, as your comment suggests?  

---

## 0 answers

