3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Harald Hanche-Olsen
    Commented Feb 27, 2011 at 9:42
  • $\begingroup$ @Harald: Shame on me that I haven't figured that out by myself. It seems that I have shown my ignorance here. $\endgroup$
    – Tomek Tarczynski
    Commented Feb 28, 2011 at 8:28

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ @Igor: Simple, clever and works. Thanks, +1. $\endgroup$
    – Tomek Tarczynski
    Commented Feb 28, 2011 at 8:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .