|
2
|
How to determine whether an intersection of a convex polytope and a simplex in $R^{n}$ is not empty? 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}.$ |
||||||||
|
|
1
|
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). |
|||
|
