0
$\begingroup$

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?

$\endgroup$

3 Answers 3

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Yes, I would like to use this, but how can I find this hyperplane given the $r_i$ and $t_i$? $\endgroup$ Jun 20, 2013 at 20:55
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jun 20, 2013 at 20:59
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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