I’ve asked a couple of CS friends this and we couldn’t figure out the answer so I’m hoping some math dopers here might have some experience with this problem.
I want an algorithm that, given a set of 3D vectors (Assume they’re unit vectors but that’s not really relevant), can you find a plane such that all the vectors lie on the same side of the plane.
The best algorithm we’ve come up with so far is:
for each pair of vectors, define the plane such that both vectors lie in the plane.
then check if every other vector lies on the same side.
but that’s an O(n^3) algorithm and I was hoping for something better as it’s in an inner loop.
It seems to me as if there should be some sort of geometric construction that could do this for me.
You can represent these vectors as points in 3D space. Wouldn’t it be possible to find the minima and maxima and thence define the plane to be above or below?
I don’t know what you mean by this. If you know the convex hull (for example, in 3-space) you have a set of triplets of points, which forms a subset of the set of original points. Any of the triplets defines a plane where all of the original points are on or to one side of the plane.
The desired plane may have oblique orientations. That’s really the problem.
If you are representing your vectors by the endpoints, and finding the convex hull of that, then that is not true. In that case, in order for the conditions of the OP to hold, the origin would have to be inside the convex hull.
Otherwise, your algorithm works for every set of vectors, right? And we know that’s not true.
I think this is what Quartz is getting at, but to be clearer about it: any finite set of vectors in R[sup]3[/sup] is bounded, thus contained in some sphere, thus all on one side of any tangent plane to that sphere. I can only see your question making sense if you mean “subspace” – a plane through the origin.
In that case, I’ll expand on Demostylus’ answer: The convex hull is the smallest convex set containing all the points. There is a subspace with the desired property if and only if the convex hull contains the origin. So, calculate the convex hull (O(n log n)) and see if (0,0,0) is in it.
Given a set of 3D vectors, find a vector such that the minimum angle between the new vector and any vector in the set is maximised. ie: place the new vector so it’s as far away from the old vectors as possible.
If you can do this, then it’s trivial to create a plane based on the new vector and test if any of the old vectors fall on the wrong side.
Okay, I have an idea but I don’t know how the math would work. Any arbitrary 3 vectors should in theory define a cone.
Seed the system by picking 3 vectors and converting it into a cone representation.
Add a new vector and check whether it’s inside the cone or outside.
If it’s in the inside,
do nothing.
If it’s outside,
if it’s in the anti-cone (That is, the cone defined by the negative of the 3 vectors)
then the set of vectors cannot form a subspace.
else
replace one of the 3 original vectors with the new vector such that all the vectors are now inside the cone.
When all the vectors are added in, the negative of the axis of the cone will be the furthest point.
The problem I have now is
a) How do you convert from 3 vectors into a cone?
b) given a new vector outside the cone, how do you choose which vector to replace?
Okay, I’ve done a bit more reading and I think I have a grasp on how to formulate the problem now. Represent each vector as a point on the unit sphere. Now, what I need to do is to find the Minimum Enclosing Surface of those points on the surface of a sphere.
problem is, I can’t seem to find much work on MES’s in a non-euclidian suface. It seems like there would be fairly obvious applications for it: Given a set of cities on earth, find the point which minimises the maximum distance you have to travel to get to any city. Anybody got any pointers?
For this I think what you want is the Delaunay triangulation of your points; this is the triangulation such that the circumcircle of each triangle contains none of the given points in its interior. In your case, since all of the vectors are unit vectors, this triangulation is essentially the same as the convex hull; so you can find this with a convex-hull algorithm that returns a list of faces (not just the extremal points). Find the faces of the convex hull of your set of unit vectors, then find the circumcenter and circumradius of each (triangular) face. The circumradius is the absolute value of the cosine of the angle between the circumcenter vector and the vectors to the three vertices of that face; and that is the best you can do for points on that face. Then pick the optimum over all faces.
Note that the circumradius only gives you |cos x|; to determine the sign you have to test whether the circumcenter vector points toward or away from the rest of your points. If toward (remaining points all on side of face away from origin), then cos x < 0; if away (remaining points all on side of face toward origin), then cos x > 0.
It’s much faster to check to see if there is any subset of vectors exist such that you know that it’s impossible to have a plane that doesn’t subdivide them. You split up the vectors into groups of three, and for each group you find the 3 planes that are cross-products of each pairing of vectors. You merge the groups together, at each step checking the planes you’ve already calculated as well as each plane that is a pairing of one vector from each group and retain all those planes that do not subdivide the group. If none exist, you’re done. If some exist, you keep only those planes and only the vectors that lie on at least one of those planes, and continue iterating.
I believe that in the worst case it’s still order O(n[sup]3[/sup]) when the input is vectors that lie on the surface of a cone. I also believe that the best implementation would be one that merged the smallest existing groups with each other at each step.
Actually, maybe it’s not O(n[sup]3[/sup]) in the worst case because you’re eliminating many planes from being tested against many vectors. I’ll think about it more.
btw: I’ve since discovered it’s called a Minimal Spanning Circle(MSC). Anyway, a MSC on a sphere can only exist if all the points lie on the same hemisphere. If you can form a MSC, that means you can cut the sphere in half such that all the points lie on one side.
It seems Delauney’s triangulation, MSC’s and convex hulls all essentially boil down into the same thing for my example. There certainly is a lot of overlap in technique.