Intersection of line and convex set

Question

Let X be a collection of n points in some moderate-dimensional space - for now, say R^5. Let S be the convex hull of X, let p be a point in S, and let v be any direction. Finally, let L = {p + lambda v : lambda a real number} be the line passing through p in direction v.

I am interested in finding a reasonably efficient algorithm for computing the intersection of S with L. I'd also be interested in hearing if it is known that no such algorithm exists! Note that this intersection can be represented by the (extreme) two points of intersection of L with the boundary of S. I'm particularly interested in finding an algorithm that behaves well when n is large.

I should say that it is easy to do this very efficiently in two dimensions. In that case, one can order the points of X in 'clockwise order' as seen from p, and then do binary search. So, the initial ordering takes O(n log(n)) steps and then further lookups take O(log(n)) steps. I don't see what the analogous algorithm should be in higher dimensions. Part of the problem is that a convex body in two dimensions has n vertices and n faces, while a convex body in 3 or higher dimensions can have n vertices but many, many more than n faces.

What language, platform or tool are you using to interpret this code/markup? "$X = { x_{1},\ldots,x_{n} }$" — NTDLS
By $X \cap L$ , are you referring to the set of points that are in your original set X, and also on the line L? Wouldn't this be as simple as checking if each point in X satisfies the equation of L? I feel like I'm missing something fundamental. — sykora
Shrug. I have no problem reading simple TeX, and I actually prefer it to reading mangled HTML math. — tmyklebu
The fact that the OP is tempted to use Tex markup rather than code formatting is a strong indicator to me that this post should be in cs.stackexchange.com rather than stackoverflow. — beaker
Thanks for the comments, and thank you Douglas for the edit. Indeed this was supposed to be Latex. I hope it is easier to read now. sykora: I may have written X \cap L for the intersection of X and L in the original. The intent (which is also the version left by Douglas) was to look for the intersection of S and L. This is harder, as it isn't so clear what equations to check. — l2c

tmyklebu tmyklebu · Accepted Answer · 2015-04-17T15:53:50

You can write a simple linear program for this. You want to minimise/maximise lambda subject to the constraint that x + lambda v lies in the convex hull of your input points. "Lies in the convex hull of" is coordinatewise equality between two points, one of which is a nonnegative weighted average of your input points such that the weights sum to 1.

As a practical matter, it may be useful to start with a handful of randomly chosen points, get a convex combination or a certificate of infeasibility, then interpret the cerificate of infeasibility as a linear inequality and find the input point that most violates it. If you're using a practical solver, this means you want to formulate the dual, switch a bunch of presolve things off, and run the above essentially as a cutting plane method using certificates of unboundedness instead. It is likely that, unless you have pathological data, you will only need to tell the LP solver about a small handful of your input points.

Intersection of line and convex set

1 Answers