4
$\begingroup$

I have two polyhedral cones represented by their rays. I am looking to find their intersection, which would also be a polyhedral cone, hopefully efficiently. Does anybody know a way to do that?

Thanks

Deepanshu

$\endgroup$
2
  • $\begingroup$ More details would help. Are you trying to find the intersection numerically or give a simple description in some sense? What kind of an answer would be acceptable? What space are you working in? $\endgroup$ Aug 19, 2014 at 19:43
  • 3
    $\begingroup$ At an REU in 2010, I was a part of a team that designed and implemented an algorithm along these lines as a part of a project to visualize piecewise flat manifolds. The relevant section of our paper begins at the bottom of page 8 at this link: math.arizona.edu/~asp/2010/… Hope something there is useful! $\endgroup$ Aug 19, 2014 at 22:41

2 Answers 2

6
$\begingroup$

Presumably you are working in $\mathbb{R}^d$ for $d > 3$. There are specialized algorithms in $d=2,3$.

Here is one route. You have, essentially, what is known as the V-representation of your polytopal cones, V=vertex. An alternate representation is the H-representation, H=halfspace, the intersection of halfspaces. If you convert each cone's V-representation to an H-representation, then you have reduced your problem to intersecting all the halfspaces defining both cones.

One can convert between V- and H-representations via a variety of software packages. E.g., it can be accomplished in R; see this link. Perhaps a better place to start is polymake; see this web page.

The intersection of halfspaces can be accomplished by a wider variety of software, including polymake and qhull.

$\endgroup$
2
$\begingroup$

Another code you may wish to try is 4ti2's rays-function. It can also be called via polymake.

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