Algorithm to check whether simplices intersect nicely Suppose that $A$ and $B$ are both $3$-simplices linearly embedded in $\mathbb{R}^3$, say with vertices in $\mathbb{Q}^3$ so that we can do computations exactly.  (I am also interested in the generalisations where the two simplex dimensions and the ambient dimension may be different and may be larger, but this will do for the moment.)  Let us say that $A$ and $B$ intersect nicely if $A\cap B$ is either empty, or is a common subsimplex of $A$ and $B$ (possibly of dimension $0$, $1$ or $2$).  What is an efficient algorithm to check whether this holds?  One can try to calculate $A\cap B$ in general by linear programming techniques, but this can be quite complicated, and it feels like there should be something much simpler for this restricted question.
 A: Here's an algorithm that works for simplices $\sigma$ and $\tau$ of arbitrary dimension in $\mathbb{R}^d$.  Let $C$ be the set of common vertices, let $A$ be the remaining vertices of $\sigma$, and let $B$ be the remaining vertices of $\tau$.  For $a\in A$ put $a^*=(a,1,0)\in\mathbb{R}^{d+2}$.  For $b\in B$ put $b^*=(-b,-1,1)$ and for $c\in C$ put $c^*=(c,1,0)$.  Now enumerate the maximal linearly independent subsets $U\subseteq A^*\amalg B^*\amalg C^*$ with $A^*\subseteq U$.  For each such subset, there is at most one way to write $(0^{d+1},1)$ as a linear combination of $U$.  If there is a solution in which all the coefficients for $U\cap(A^*\amalg B^*)$ are nonnegative, then $\sigma$ and $\tau$ do not intersect in the right way.  If this test is passed for all $U$ then $\sigma$ and $\tau$ do intersect correctly.  
Consider the case of two $3$-simplices in $\mathbb{R^3}$ with no common vertices.  There are $4$ sets $U$ with $|U\cap A^*|=1$ and $U\supset B^*$.  The tests for these $U$ check whether any vertex of $\sigma$ lies in $\tau$.  There are $24$ sets $U$ with $|U\cap A^*|=2$ and $|U\cap B^*|=3$.  The tests for these $U$ check whether any edge of $\sigma$ meets any face of $\tau$.   There are further tests with the roles of $\sigma$ and $\tau$ reversed, which brings us to $56$; these are as in Joseph O'Rourke's comment.  One sometimes needs a few extra tests if there are unusual linear relations between the edge vectors of $\sigma$ and $\tau$.  In the generic case we need to do $56$ row reductions of matrices of shape $5\times 6$.  That still seems like quite a lot of work, but perhaps it is unavoidable.
