Maximizing angles for lines coming out of a point

[df606]

I'm working on a programming project, and I've got this problem I don't really know how to describe or approach.

Given a point and a number of lines extending from the point, I want to find the best angle (in 3d) to maximize the distances between the lines. The 2D equivalent would be to simply divide 360 degrees by the number of lines.

This is kind of vague but I can't think of how else to describe this. Hopefully this much is understandable.

 

[gsal]

Oh, it is clear enough...perfect analogy.

Never had thought about this problem.

Don't know how to do it, either, you know, in a deterministic manner...the only thing that occurs to me is to take as many unit length vectors as lines you are trying to accommodate and re-orient them around to minimize the grand total of the summation of the addition of every two vectors...does that make sense? is what I am saying clear enough?

 

[df606]

I see what you're saying. In other words, if you laid all the vectors head to tail, you would try to get a magnitude as close to zero as possible.

I think I see a way to solve this recursively. Start with one vector in some arbitrary angle. Add another vector, starting at the tail of the previous vector, with the same magnitude but opposite direction.

Every time you add a vector, you first remove a vector. Create two vectors that add up to opposite direction and same magnitude as the sum of all the other vectors.

There's something wrong with this, though, I think. I'm going to play around with it a bit and see what I get.

Edit: epenguin, that's exactly what I was trying to say, that is, I want to maximize the lengths of the chords. I'm not sure if my solution does that or if it even does what I imagined it to do.

 

[MisterX]

the only thing that occurs to me is to take as many unit length vectors as lines you are trying to accommodate and re-orient them around to minimize the grand total of the summation of the addition of every two vectors?

That won't work.

For example, with three lines, { \hat{x}, \hat{y}, \hat{z} } is a correct solution. The sum of the magnitudes of the addition of every combination of two vectors is 3 * sqrt(2)
I assume this is what you meant.
Consider the set of vectors { { \hat{x}, -\hat{x}, \hat{y} } }
The sum of the magnitudes of the addition of every combination of two vectors is 2 * sqrt(2).
Both those values are less, but yet this is not a correct solution, because \hat{x} and -\hat{x} represent the same line.

What may be correct is the set of N unit vectors that minimizes

\sum_{i = 1}^{ N} \sum_{j = i}^{ N} (\hat{v}_{i} \cdot \hat{v}_j)^{2}

or that maximizes

\sum_{i = 1}^{ N} \sum_{j = i}^{ N} \left\| \hat{v}_{i} \times \hat{v}_j \right\|

 

[gsal]

df606:

I don't think you are saying the same thing I meant to say...

You do not add ALL the vectors in one shot; instead, you take all possible combinations of two-at-a-time, calculate the addition of those individual pairs and then add all those numbers up.

Then, you start re-orienting the vectors in an attempt to minimize the grand total calculated above.

Actually, if you can tell which vectors are 'neighbors', you only need to determine the addition of every vector with every other 'adjacent' vector (and then add those for a gran total)...since vectors should be equidistant from each other, it should be easy to tell which vectors are the ones surrounding a given vector...this should reduce the number of two-at-a-time combinations that are of interest.

MissterX: Let me think a bit to what you just said...

 

[epenguin]

It's late and I am error-prone.

First you are going to have to define what you mean by 'maximise the distances between the lines'. In fact you have not even defined what you mean by 'distances between the lines'. In your planar example perhaps you mean, drawing a circle with your given point as centre, then maximise the sum of the lengths of all the chords?

Are you sure your solution maximises this, not minimises?

The 3-D equivalent would be with sphere. Then I'm sure the points as vertices of perfect solids would give your maximum or minimum for your measure. But that only works for 4, 8, 12, 20 and 60 points. Symmetry corresponds to extrema. But more to minima. Anyway there are a variety of nextmost symmetrical solids that might be solutions for other numbers. In general I find it hard to see, but maybe I am missing some simple point.

 

[gsal]

MisterX:

o.k., I see what you think I am saying and my previous post should have clarify that...I never said to simply take ALL vectors and add them up. I said to take all the two-at-a-time results and add THOSE up and keep doing it until it is minimized.

Your x,y,z exercise results in this: There are 6 vectors and they are 90 degrees apart; so, the addition of just two is sqrt(2). Number of two-at-a-time combinations out of 6? 15! Grand total= 15 x sqrt(2)=21.21 this is the number to match...but this is an easy problem we knew the answer to ahead of time. Move any of those vectors, re-calculate, and you should get a larger number.

Considering the vectors x, -x, y...we can see that they are not equidistant..but let's pretend that we don't know anything...let's add the combinations= 0 + sqrt(2) + sqrt(2) = 2*sqrt(2)=2.8284 ...can these vectors be re-oriented to yield a smaller number...sure...when they are 120 degrees appart...which is the solution for 3 vectors= sqrt(3)/2 +sqrt(3)/2 +sqrt(3)/2 = 2.598

and so on...

Now, because of the symmetry of the problem, I think your formulas will work, too...and now that I see your latex, I think what I am proposing would look like this:


\sum_{i = 1}^{ N} \sum_{j = i}^{ N} (\hat{v}_{i} + \hat{v}_j)

I think it would work too.

 

[MisterX]

MisterX:

o.k., I see what you think I am saying and my previous post should have clarify that...I never said to simply take ALL vectors and add them up. I said to take all the two-at-a-time results and add THOSE up and keep doing it until it is minimized.

That's what I assumed you meant, and I demonstrated that it didn't work.

Your x,y,z exercise results in this: There are 6 vectors and they are 90 degrees apart;so, the addition of just two is sqrt(2). Number of two-at-a-time combinations out of 6?

But you wrote "as many unit length vectors as lines you are trying to accommodate", not twice as many. But even if there are twice as many (every vector with its negation), the adding method still won't work (minimized).

15! Grand total= 15 x sqrt(2)=21.21

This is incorrect, for example \left\| \hat{x} + -\hat{x} \right\| = 0
and not sqrt(2).


Anyway here is a demonstration that even with double the number of vectors minimizing

\sum_{i = 1}^{ N} \sum_{j = i}^{ N} \left\| \hat{v}_{i} + \hat{v}_j \right\|

doesn't result in the correct answer.


For the set of vectors \hat{x}, \hat{y}, \hat{z}, -\hat{x}, -\hat{y}, -\hat{z}
\sum_{i = 1}^{ N} \sum_{j = i}^{ N} \left\| \hat{v}_{i} + \hat{v}_j \right\| \approx 45.941125496954270

For the set of vectors \hat{x}, \hat{x}, \hat{x}, -\hat{x}, -\hat{x}, -\hat{x}

\sum_{i = 1}^{ N} \sum_{j = i}^{ N} \left\| \hat{v}_{i} + \hat{v}_j \right\| = 36

which is less than the first set of six vectors, yet we know this set of vectors is wrong.

Thefore, this is not the expression to minimize. Perhaps maximizing it would work instead.



Oh and

\left\|\sum_{i = 1}^{ N} \sum_{j = i}^{ N} (\hat{v}_{i} + \hat{v}_j) \right\|

won't work with miminizing or maximimizing

 

[gsal]

By the way, I feel like we are still a bit ouf of frequency as to what a line is...from the OP, I understood that he/she wants the 'lines' starting at a common point and grow 'radially' out. Under this condition, not every vector has a corresponding opposite one; for example, for every odd number of 'lines' extending from the point (as described by the OP)...for 3, 5, 7, 9 and so on. That much is clear, correct?

In any case, you are correct, I do have a my mistake in my numbers...for the unit vectors x, y, z, -x, -y, -z exercise, 3 of the pairs add to zero, so, the grand total is actually 12*sqrt(2) = 16.97

But then, my own calculation reveals that for x, x, x, -x, -x, -x, the grand total is 12, which is less than 16.97...

...so, my suggestion does not work.

Out of curiosity, though, why are you and I calculating totally different numbers? Granted, I am dusty on this and I may be the one totally wrong, but would you kindly detail how you come about calculating 45.94? for the x, y, z, -x, -y -z exercise?

If I have 6 unit vectors all 90 degrees apart from each other, the vectorial sum of every two at 90 degrees apart is sqrt(2), correct? And this happens 12 times...so, 12*sqrt(2) = 16.97.

So, how do you get 45.94 for x, y, z, -x, -y -z.

and how do you get 36 for x, x, x, -x, -x, -x? For this exercise, the vectorial sums of two vectors at a time yields 2 six times and 0 (zero) nine times...that's a grand total of 12.

Are you using some kind of program? Maybe the limits of the summation symbols need to be adjusted to
i from 1 to N-1
j from i+1 to N

 

[MisterX]

By the way, I feel like we are still a bit ouf of frequency as to what a line is...from the OP, I understood that he/she wants the 'lines' starting at a common point and grow 'radially' out. Under this condition, not every vector has a corresponding opposite one; for example, for every odd number of 'lines' extending from the point (as described by the OP)...for 3, 5, 7, 9 and so on. That much is clear, correct?

That's not what I usually consider a line, but I rereading the OP, it may be what the author meant.

With this interpretation, the problem seems similar to determining the bond angles for VSEPR theory (with no lone electron pairs).

http://en.wikipedia.org/wiki/Vespr#AXE_method

It may be worth noting that the angles are not always equal; for example with steric number 5, there are both 120 degree and 90 degree angles.

If a reader of this post knows of the math relating to these VSEPR angles, perhaps they might post something about this.

Are you using some kind of program? Maybe the limits of the summation symbols need to be adjusted to
i from 1 to N-1
j from i+1 to N

I thought of posting those limits too. I think the sums would behave in a similar manner, but these limits would require less work.

I used MatLab to do those calculations, with limits 1 to N for both indices.