Spreading vectors around an area

[wbrigg]

hey all,

I was wandering if there was a way to spread vectors as evenly as possible through space (all originating from the same point.

In 2D, this is easy, i just divide a unit circle into the number of peices i require (or in the specific case I'm looking at it for, i divide the 1^st quadrant into that many peices).

In 3D it gets harder though. i figured it's effectively the same thing as spreading dots evenly around a sphere, and it seems there's no way (on the internet) to do this other than via algorithms.

would it be possible to achieve what I'm looking for using Matrices?

i.e.

\begin{pmatrix}<br /> a1\\<br /> a2\\<br /> a3<br /> \end{pmatrix}<br /> <br /> \begin{pmatrix}<br /> b1\\<br /> b2\\<br /> b3<br /> \end{pmatrix}<br /> <br /> \begin{pmatrix}<br /> c1\\<br /> c2\\<br /> c3<br /> \end{pmatrix}<br /> <br />

are my vectors i want to spread out as much as possible (all the same length).

if i take
<br /> \begin{pmatrix}<br /> a1&amp;b1&amp;c1\\<br /> a2&amp;b2&amp;c2\\<br /> a3&amp;b3&amp;c3<br /> \end{pmatrix}<br />
and it's transpose, and multiply them, i'll get a symetric matrix with 1s down the leading diagonal (dot product with itself) and numbers less than one (other dot products) everywhere else.

what I'm asking is if there's a way to minimise all the entries of this matrix so that the sum of them all is as small as possible? And would that result in having my vectors evenly spread out around the space?

 

[wbrigg]

have i put this in the wrong thread/forum thing?

 

[HallsofIvy]

I don't think anyone understands what you are trying to do. If it is just "find n points evenly distributed on a unit sphere" then you probably want to use polar coordinates with \rho set equal to 1. Since a circle of lattitude \phi has radius sin(\phi) and so circumference 2\pi sin(\phi) you will want to distribute, say, n₁ values of \phi evenly between 0 and \pi and distribute n₂= floor(n₁sin(\phi) on each circle of "latitude" \phi where n_1n_2= n_1^2 sin(\phi)= n.

 

[wbrigg]

i'm looking for a way to distribute n points so that they cover all directions evenly if you draw a line from the origin to each point. In 3 dimensions this corresponds to evenly spacing points around a sphere, and in two dimensions around a circle. In one dimension it's just left and right (or up and down, depends on what your one dimension is).


From browsing google and such I've found that the way people do it for a sphere is to have a spiral which goes from on point on the sphere to another on the other side, and then have the spiral such that the distance between the spirals is the same as the distance between the points. This method is a good approximation, but it's not ideal. And it cannot be altered (in anyway i see) to work in higher dimensions.

some numbers of vectors are easy to space around,

i.e. in 1D, the two unit vectors would be (1) and (-1)

So i'd have two matrices, (1,-1) and it's transpose. then I'd multiply the transpose by the first to get

<br /> \begin{pmatrix}<br /> 1&amp;-1\\<br /> -1&amp;1<br /> \end {pmatrix}<br />

If i do it in 2D, then I'm now spacing points around a circle.
Spacing 2 Points around a circle gives the same matrix as above.

Spacing 3 points around a circle gives:
<br /> \begin{pmatrix}<br /> 1&amp;-0.5&amp;-0.5\\<br /> -0.5&amp;1&amp;-0.5\\<br /> -0.5&amp;-0.5&amp;1<br /> \end {pmatrix}<br />

4 Points:
<br /> \begin{pmatrix}<br /> 1&amp;0&amp;-1&amp;0\\<br /> 0&amp;1&amp;0&amp;-1\\<br /> -1&amp;0&amp;1&amp;0\\<br /> 0&amp;-1&amp;0&amp;1<br /> \end {pmatrix}<br />

These matrices have the top values as Cos(a2Pi/b) where b is the number of points being spread an a just counts from 1 up to b.

No matter how many dimensions you do this in you always get a b by b matrix.

Extending the Cos thing from above to a sphere would give the matrix of

<br /> \begin{pmatrix}<br /> 1&amp;0.5&amp;-0.5&amp;-1&amp;-0.5&amp;0.5\\<br /> 0.5&amp;1&amp;0.5&amp;-0.5&amp;-1&amp;-0.5\\<br /> -0.5&amp;0.5&amp;1&amp;0.5&amp;-0.5&amp;-1\\<br /> -1&amp;-0.5&amp;0.5&amp;1&amp;0.5&amp;-0.5\\<br /> -0.5&amp;-1&amp;-0.5&amp;0.5&amp;1&amp;0.5\\<br /> 0.5&amp;-0.5&amp;-1&amp;-0.5&amp;0.5&amp;1<br /> \end {pmatrix}<br />

Now what vectors would i need to create that matrix? Obviously there are Three pairs of vecotrs differing only in their magnitude. and a Dot product of 60 degrees corresponds to the two vectors being at 60 Degrees to one another. The best way to space 6 points aroudn a sphere would be to have two triangles top and bottom, with one rotated 30 degrees... And, and it seems like that is what these vectors suggest. I'm asking would this continue to work in Higher dimensions and with more points?

 

[olliemath]

I get what you're saying. I think it's clear (although I could be wrong and it would be hard to prove it) that the optimum arangement is when the angle between each pair of vectors is the same - otherwise you have to introduce some sort of measure of 'spaced-outness' - which sounds like a drugs test to me.

If we just deal with unit vectors then for each pair we must have v_i\cdot v_j = \cos\theta, where theta is the angle we want. So if we have n of them we can form the 3 by n matrix A=(v_1,\ldots,v_n), where we're using column vectors. Given what we have just said, we must have
A^TA=\left(\begin{array}{cccc}<br /> 1 &amp; C &amp; \ldots &amp; C \\<br /> C &amp; 1 &amp; \ldots &amp; C \\<br /> \vdots &amp; &amp; \ddots &amp; \vdots \\<br /> C &amp; C &amp; \ldots &amp; 1 \\ \end{array} \right),
where C=\cos\theta, since the ij-th entry is just the dot product of the i-th and j-th vectors.
So the problem reduces to finding a 3 by n matrix A (if it exists) with this property?

I think it should be do-able, but don't have the time right now (going to a 5-day music festival - and it just started pouring with rain, grr..) Have you tried looking at some chemistry (or related) sites? This reminds me of drawing e.g. the skeletal structure of CH_4 in high school.. all the 'bonds' have to be equally spaced. Search for molecular geometry or VSEPR

 

[wbrigg]

off to reading eh.


If by "angle between each pair of vectors" you mean each vector and it's nearest neighbor, then it would only work for a 2D space (or 2D plane in higher dimensions). i.e. you could just arrange the points around an equator of the sphere and it would satisfy your condition.


I'm essentially looking for a way to create a set of vectors where this:

\sum^{n}_{a=0}\sum^{n}_{b=0}\vec{x}_{a}\vec{x}_{b} is Minimised.

If you have vectors with 3 Elements, it's 3D, 2 elements is 2D. 20 Elements would be a 20 Dimensional *thing*. The matrix you get in the end is always an n\times n matrix, where n is the number of vectors.