# An intersection of a convex polytope and a simplex

How to determine whether an intersection of a convex polytope and a simplex in $R^{n}$ is not empty?
The polytope is given in a halfspace representation.

I'm aware that there are some algorithms which work in $R^{2}$ and $R^{3}$, but I don't know any that would work in $R^{n}.$

-
Please forgive me if I am showing my ignorance here, but isn't this the first step in the simplex algorithm for solving linear programming problems? – Harald Hanche-Olsen Feb 27 '11 at 9:42
@Harald: Shame on me that I haven't figured that out by myself. It seems that I have shown my ignorance here. – Tomek Tarczynski Feb 28 '11 at 8:28

I find @Harald's comment a little mysterious, but an obvious algorithm for the OP is to observe that a simplex is the intersection of $n+1$ halfspaces $h_1, \dotsc, h_{n+1},$ and then check that $Q=P \cap h_1 \cap h_2 \dots \cap h_{n+1}$ [where $P$ is your polytope) is nonempty. This last problem is a standard linear programming problem (and usually solving this "feasibility" problem is the first half of the simplex algorithm, which may be what @Harald is saying).