MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}.$

share|cite|improve this question
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
up vote 1 down vote accepted

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).

share|cite|improve this answer
@Igor: Simple, clever and works. Thanks, +1. – Tomek Tarczynski Feb 28 '11 at 8:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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