Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer

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|improve this answer
    
@Igor: Simple, clever and works. Thanks, +1. –  Tomek Tarczynski Feb 28 '11 at 8:29
add comment

Your Answer

 
discard

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.