Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

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

share|improve this answer
    
Yes, I would like to use this, but how can I find this hyperplane given the $r_i$ and $t_i$? –  Stephen Sturgeon Jun 20 '13 at 20:55
add comment

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

share|improve this answer
    
This has been my strategy so far. I was hoping there was some easier check like a determinant of some matrix or something similar that would do the trick. –  Stephen Sturgeon Jun 20 '13 at 20:59
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.