I'm looking for an algorithm to test if an N-dimensional object (defined by the convex hull of N+1 vertices) and an M-dimensional object (defined by the convex hull of M+1 vertices) intersect within L-dimensional space (where L is greater than or equal to both N and M). Ignore degenerate cases.
For example, it could test if a line segment and a triangle intersect in 3D space, and it could also test if two 4D objects intersect in 4D space.
I have been researching and thinking about this problem for a while, and have not found the answer yet, though it seems possible. So far my approach is to define the objects parametrically, and then check the system of equations for a solution.
Here is what I have so far: Object 1 has N dimensions, is defined by N+1 vertices, and exists in L dimensional space. Vertex 1 is the "origin" O1. N vectors V1 through Vn are defined by the difference of O1 and each of the other N vertices. N scalar parameters P1 through Pn are paired with the N vectors. So now every point in object 1 is defined by: O1 + sum(Pi*Vi, i = 1:N) such that "Pi >= 0" AND "sum(Pi, i = 1:N) <= 1". We have a similar definition for Object 2, with M+1 vertices also in L dimensional space, with vectors W1 through Wm, and scalars Q1 through Qm. This provides a system of L*(N+M) equations and L+N+M unknowns. Now my strategy is to reduce the system and test to see if there is a solution such that: "Pi >= 0" AND "sum(Pi, i = 1:N) <= 1" AND "Qi >= 0" AND "sum(Qi, i = 1:N) <= 1".
Any thoughts on how to proceed? I'm hoping that someone has done this already, and I won't have to re-invent the wheel.