# Advanced Vectors Question **URL:** \ **Category:** Factual Questions\ **Created:** [May 16, 2005, 11:24am UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047 "2005-05-16T11:24:17Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [May 16, 2005, 11:24am UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/1 "2005-05-16T11:24:17Z")
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. ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [May 16, 2005, 12:08pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/2 "2005-05-16T12:08:45Z")
You can find the convex hull of an arbitrary set of points in O(\*n \*log _n_) operations. That’s better than O(_n_[sup]3[/sup]). Google “convex hull”. ---
**Author:** ![Quartz](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/quartz/32/267_2.png) [@Quartz](https://boards.straightdope.com/u/Quartz)\ **Post date:** [May 16, 2005, 12:10pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/3 "2005-05-16T12:10:09Z")
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? ---
**Author:** ![Quartz](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/quartz/32/267_2.png) [@Quartz](https://boards.straightdope.com/u/Quartz)\ **Post date:** [May 16, 2005, 12:43pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/4 "2005-05-16T12:43:01Z")
> [@Desmostylus](#): > > You can find the convex hull of an arbitrary set of points in O(\*n \*log _n_) operations. That’s better than O(_n_[sup]3[/sup]). Google “convex hull”. Ah yes, but the OP wants a plane. I suppose you could have the plane normal to the peak or trough. ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [May 16, 2005, 12:59pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/5 "2005-05-16T12:59:06Z")
> [@Quartz](#): > > …plane normal to the peak or trough. 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. ---
**Author:** ![RM\_Mentock](https://avatars.discourse-cdn.com/v4/letter/r/e274bd/32.png) [@RM\_Mentock](https://boards.straightdope.com/u/RM_Mentock)\ **Post date:** [May 16, 2005, 1:38pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/6 "2005-05-16T13:38:30Z")
> [@Quartz](#): > > 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? The desired plane may have oblique orientations. That’s really the problem. > [@Desmostylus](#): > > 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. 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. ---
**Author:** ![Desmostylus](https://avatars.discourse-cdn.com/v4/letter/d/c57346/32.png) [@Desmostylus](https://boards.straightdope.com/u/Desmostylus)\ **Post date:** [May 16, 2005, 1:55pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/7 "2005-05-16T13:55:53Z")
If you know of a better answer, then cough it up. :rolleyes: ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [May 16, 2005, 3:06pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/8 "2005-05-16T15:06:37Z")
> [@Shalmanese](#): > > 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. Do you mean “plane” or “subspace”? 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. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [May 16, 2005, 3:08pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/9 "2005-05-16T15:08:56Z")
Okay, slightly harder problem. 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. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [May 16, 2005, 3:10pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/10 "2005-05-16T15:10:27Z")
> [@Mathochist](#): > > Do you mean “plane” or “subspace”? > > 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. Sorry, yes, I mean’t subspace or plane running through the origin. It’s harder trying to do this with words than on paper :P. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [May 16, 2005, 3:28pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/11 "2005-05-16T15:28:58Z")
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? ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [May 16, 2005, 4:38pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/12 "2005-05-16T16:38:17Z")
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](http://www.cs.brown.edu/people/tor/java/mec/) 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? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [May 16, 2005, 4:46pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/13 "2005-05-16T16:46:04Z")
> [@Shalmanese](#): > > 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](http://www.cs.brown.edu/people/tor/java/mec/) of those points on the surface of a sphere. Would that be guaranteed to give you a subspace? ---
**Author:** ![MechE](https://avatars.discourse-cdn.com/v4/letter/m/a698b9/32.png) [@MechE](https://boards.straightdope.com/u/MechE)\ **Post date:** [May 16, 2005, 4:51pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/14 "2005-05-16T16:51:07Z")
Just sketching on a sheet of paper, how about: 1. assume all start at the origin. 2. assume no colinear vectors Add the three vectors together Use this vector as the normal to the plane. For example: \<1,0,0\> + \<0,1,0\> + \<0,0,1\> = \<1,1,1\> which is normal to a plane on which all 3 vectors are on one side of it. sketch it out and it might work. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [May 16, 2005, 4:53pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/15 "2005-05-16T16:53:12Z")
> [@MechE](#): > > Just sketching on a sheet of paper, how about: > > 1. assume all start at the origin. > 2. assume no colinear vectors > > Add the three vectors together > Use this vector as the normal to the plane. > > For example: > > \<1,0,0\> + \<0,1,0\> + \<0,0,1\> = > \<1,1,1\> which is normal to a plane on which all 3 vectors are on one side of it. sketch it out and it might work. If you had six vectors a, a’, b, b’, c, c’ with a, b, c pairwise orthogonal and a + a’, b + b’, c + c’ all very nearly 0, that wouldn’t work. ---
**Author:** ![MechE](https://avatars.discourse-cdn.com/v4/letter/m/a698b9/32.png) [@MechE](https://boards.straightdope.com/u/MechE)\ **Post date:** [May 16, 2005, 5:03pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/16 "2005-05-16T17:03:04Z")
Hmm, for some reason I saw it as on having 3 3d vectors, my bad, back the drawing board… ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [May 16, 2005, 6:23pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/17 "2005-05-16T18:23:59Z")
> [@Shalmanese](#): > > Okay, slightly harder problem. > > 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. 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. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [May 16, 2005, 6:28pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/18 "2005-05-16T18:28:51Z")
> [@Shalmanese](#): > > 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. 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. ---
**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\ **Post date:** [May 16, 2005, 6:36pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/19 "2005-05-16T18:36:10Z")
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. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [May 16, 2005, 6:57pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/20 "2005-05-16T18:57:22Z")
> [@ultrafilter](#): > > Would that be guaranteed to give you a subspace? 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. [Next page](https://boards.straightdope.com/t/advanced-vectors-question/304047.md?page=2)