How to determine if two rational cones intersect?

Question

Let $$\displaystyle C_1=C(r_1,...,r_{n_1})=( x\in \mathbb{R^d}|x=\sum_{i=1}^{n_1}\lambda_i r_i, \lambda_i\in \mathbb{R_{>0}})$$ $$\displaystyle C_2=C(t_1,...,t_{n_2})=(x\in \mathbb{R^d}|x=\sum_{i=1}^{n_2}\lambda_i t_i, \lambda_i\in \mathbb{R_{>0}})$$ Then assume that the $r_i$ and $t_i$ are integer points in $\mathbb{R^d}$. Then $C_1$ and $C_2$ are the cones over these set of points. I realize if some of the $r_i$ are equal to some of the $t_i$ then they will intersect on the boundary. Is there a good way to determine if these two cones intersect in their interior?

Answer 1

The so-called separation property of convex cones tells you that $C_1$ and $C_2$ have disjoint interiors if and only if there is a hyperplane separating them. Namely, there exists $\mathbf{y}\in \mathbb{R}^d$ such that $\langle\mathbf{y},\mathbf{r}_i\rangle\ge 0$ for all $i=1,\ldots,n_1$ and $\langle\mathbf{y},\mathbf{t}_i\rangle\le 0$ for all $i=1,\ldots,n_2$.

Answer 2

I'm assuming by interior you mean relative interior. If not just check first that both generating sets span the full space -- if not, one cone has empty topological interior and so the topological interiors cannot intersect.

For relative interior, this can be formulated as a system of linear inequalities. Basically you want to find $\lambda_i,\mu_j\geq 1$ and $\sum_i \lambda_i r_i = \sum_j \mu_it_i$. Clearly any solution gives a common element of both relative interiors. Conversely, any common element of both relative interiors can be scaled until all coefficients are at least one and remain in the cone. You can efficiently search for such coefficients using a linear programming solver (with any objective function).

Answer 3

As Yoav Kallus suggests you can also view this problem as finding a hyperplane which separates the $r_i$ from the $t_j$. For this you can use any algorithm for computing a linear classifier, such as the perceptron algorithm, or one of the algorithms for support vector machines, etc.