'Generalized spiral points': further improvement
sa...@kt-algorithms.com
'generalized spiral points' procedure by Rakhmanov, Saff and Zhou (2).
For n>3, the spiral can be further improved in terms of its potential
energy by ensuring a greater spacing between the two polar points and
their immediate neighbors, and then squeezing the remaining points
closer together.
In the original algorithm (2), the point index k is used to calculate
h as follows:
h(k) = -1 + 2 (k-1)/(n-1)
Here we propose using instead:
h(k) = -1 + 2 (k'-1)/(n-1)
where k' is defined as a linear function of k so that for:
k = 2 : k' = 2+p
k = n-1: k' = n-1-p
where p is a number for which the value 1/2 seems to be a good choice.
Summarizing, the modified algorithm, also including the radius
adjustment described in (1), may be stated like this:
Initialize:
p = 1/2
a = 1 - 2*p/(n-3)
b = p*(n+1)/(n-3)
r(1) = 0
theta(1) = pi
phi(1)) = 0
Then for k stepping by 1 from 2 to n-1:
k' = a*k + b
h(k) = -1 + 2*(k'-1)/(n-1)
r(k) = sqrt(1-h(k)^2)
theta(k) = arccos(h(k))
phi(k) = [phi(k-1) + 3.6/sqrt(n)*2/(r(k-1)+r(k))] (mod 2*pi)
Finally:
theta(n) = 0
phi(n) = 0
Referring to the fractional improvement of the potential energy
defined in (1), but now letting E'(s,n) denote the measured energy of
the modified algorithm described here, these results were obtained:
n dE(-1,n) dE( 0,n) dE(+1,n)
---------------------------------
4 0.258807 0.118277 -0.055751
5 0.514698 0.383236 0.159281
6 0.681686 0.641615 0.587628
7 0.558039 0.510670 0.454153
8 0.524154 0.410367 0.177721
9 0.454853 0.298777 -0.062143
10 0.418512 0.259737 -0.144682
11 0.457363 0.321711 -0.029813
12 0.490264 0.396416 0.197726
13 0.479298 0.420625 0.360777
14 0.469588 0.418675 0.388954
15 0.480994 0.416766 0.331010
16 0.480059 0.396306 0.225399
17 0.458787 0.364193 0.125613
20 0.468736 0.391200 0.194450
25 0.467504 0.425176 0.380207
30 0.447911 0.396361 0.246581
50 0.429747 0.430728 0.491198
100 0.394210 0.424880 0.506148
200 0.352513 0.417850 0.583238
500 0.223441 0.319617 0.617322
1000 0.142754 0.236479 0.599659
2000 0.086171 0.163851 0.564971
5000 0.041311 0.092192 0.497960
10000 0.022382 0.055459 0.433520
20000 0.011245 0.030566 0.353323
The improvement can be illustrated in a very direct way by calculating
the smallest nearest neighbor Euclidean point-to-point distance
divided by the largest such distance:
-----------------------------------------
n dmin/dmax
Ref. 2 Ref. 1 This posting
-----------------------------------------
4 1.0000 1.0000 1.0000
5 0.7071 0.7071 0.8660
6 0.7071 0.7071 0.8321
7 0.6442 0.6298 0.7814
8 0.6192 0.6221 0.7680
9 0.6042 0.6124 0.7551
10 0.5939 0.6074 0.7475
11 0.5865 0.6016 0.7399
12 0.5807 0.5982 0.7373
13 0.5774 0.5943 0.7310
14 0.5793 0.5918 0.7273
15 0.5758 0.5890 0.7252
16 0.5728 0.5871 0.7212
17 0.5703 0.5850 0.7183
20 0.5686 0.5806 0.7123
25 0.5626 0.5755 0.7057
30 0.5583 0.5722 0.7021
50 0.5562 0.5655 0.6947
100 0.5509 0.5605 0.6865
200 0.5530 0.5580 0.6834
500 0.5488 0.5566 0.6816
1000 0.5504 0.5561 0.6810
2000 0.5465 0.5558 0.6807
5000 0.5463 0.5557 0.6805
10000 0.5463 0.5556 0.6805
20000 0.5463 0.5556 0.6804
Actually, the ratio dmin/dmax can be brought closer to unity by
increasing the value of p; however, this causes an increase in the
potential energy.
1. Knud Thomsen: 'Generalized spiral points': a slight adjustment,
sci.math, Feb. 6, 2007.
http://groups.google.com/group/sci.math/browse_thread/thread/327a68f46940226e
2. Rakhmanov, Saff and Zhou: Minimal Discrete Energy on the Sphere,
Mathematical Research Letters, Vol. 1 (1994), pp. 647-662.
www.math.vanderbilt.edu/~esaff/texts/155.pdf
Best regards,
Knud Thomsen
Geologist
Michael Orion
So, you put a point at the south and north poles and then space the other points along the spiral that connects the south and north poles. I have found that it works out nicely if you space the points along the sprial starting "half a step" from the south pole and ending "half a step" from the north pole. The slope of the spiral is set so that the distance (on the sphere) between turns of the spiral equals (approximately) the distance between points along the spiral. To wit:
h(k) = -1 + (2*k - 1)/n, k = 1, 2, ..., n
phi(k) = arccos(h(k))
theta(k) = sqrt(n*pi)*phi(k)
I have not calculated the potential energy for this set of points, but using some ad hoc measures I found it worked better than that of Rakhmanov, Saff, and Zhou.
- MO
sa...@kt-algorithms.com
> > slight adjustment,
> > sci.math, Feb. 6, 2007.
> >http://groups.google.com/group/sci.math/browse_thread/
> > thread/327a68f46940226e
>
> > 2. Rakhmanov, Saff and Zhou: Minimal Discrete Energy
> > on the Sphere,
> > Mathematical Research Letters, Vol. 1 (1994), pp.
> > 647-662.
> >www.math.vanderbilt.edu/~esaff/texts/155.pdf
>
> > Best regards,
>
> >KnudThomsen
> > Geologist
>
> So, you put a point at the south and north poles and then space the other points along the spiral that connects the south and north poles. I have found that it works out nicely if you space the points along the sprial starting "half a step" from the south pole and ending "half a step" from the north pole. The slope of the spiral is set so that the distance (on the sphere) between turns of the spiral equals (approximately) the distance between points along the spiral. To wit:
>
> h(k) = -1 + (2*k - 1)/n, k = 1, 2, ..., n
> phi(k) = arccos(h(k))
> theta(k) = sqrt(n*pi)*phi(k)
>
> I have not calculated the potential energy for this set of points, but using some ad hoc measures I found it worked better than that of Rakhmanov, Saff, and Zhou.
>
>
> - Show quoted text -
Congratulations, Michael, the performance of your spiral is wonderful!
Below I have listed the fractional improvement in the potential
energies.
As you can see, there may be convergence problems; however, up to
n=1000 or so, it's a clear winner!
n dE(-1,n) dE( 0,n) dE(+1,n)
---------------------------------
4 1.016003 0.998061 0.978941
5 0.994863 0.983104 0.965851
6 0.997821 0.987821 0.968939
7 0.956292 0.954012 0.953839
8 0.972033 0.970475 0.971314
9 0.951089 0.950849 0.955824
10 0.929004 0.931678 0.940895
11 0.944520 0.944802 0.946556
12 0.943331 0.942960 0.943346
13 0.917583 0.921043 0.930969
14 0.912444 0.917758 0.933775
15 0.927196 0.932321 0.948033
16 0.922047 0.927721 0.944901
17 0.898189 0.906725 0.929243
20 0.905544 0.912757 0.928173
25 0.887739 0.900195 0.929920
30 0.864829 0.880159 0.911971
50 0.797741 0.828353 0.890343
100 0.723661 0.773931 0.869622
200 0.516838 0.616602 0.809971
500 0.388356 0.498151 0.766601
1000 0.181868 0.298455 0.672691
2000 0.053534 0.151897 0.587207
5000 -0.073779 -0.008272 0.459292
10000 -0.159125 -0.116398 0.339511
20000 -0.094132 -0.071488 0.289332
Best regards
Knud Thomsen
sa...@kt-algorithms.com
wrote:
>
> - Show quoted text -
Clarification:
1. For n=4, one may get the impression that Michael's spiral points
perform better than the ideal configuration!
This is an artefact due to the fact that I have, as a matter of
convenience, used the smooth, approximate function from (2) for the
minimum energy.
2. I'm sure Michael's algorithm converges for n->infinity; however, it
may do so at a slower rate than mine or the original one of Rakhmanov
et. al.
Knud Thomsen
Michael Orion
Knud,
Glad you liked the algorithm, but I must credit to
Bauer, Robert, "Distribution of Points on a Sphere with Application to Star Catalogs ", Journal of Guidance, Control, and Dynamics, January-February 2000, vol.23 no.1 (130-137).
What I particularly like about Bauer's algorithm is that it is deterministic (is there a better word?) rather than iterative. Bauer also defines some nice measures of uniformity based on the Voronoi diagram.
What does dE(-1,n), dE(0,n), and dE(+1,n) mean? I do not understand what the first argument represents.
- MO
sa...@kt-algorithms.com
> > On Feb 26, 10:16 am, "s...@kt-algorithms.com"
> > <s...@kt-algorithms.com>
> > wrote:
> > > On Feb 25, 10:09 pm, Michael Orion
> > <beewo...@hotmail.com> wrote:
>
> > > > > In a recent posting (1) I proposed a slight
> > > > > adjustment to the
> > Rakhmanov,
> > > > > Saff and Zhou (2).
>
> > > > > slight adjustment,
> > > > > sci.math, Feb. 6, 2007.
>
> > >http://groups.google.com/group/sci.math/browse_thread
> > /
> > > > > thread/327a68f46940226e
>
> > > > > 2. Rakhmanov, Saff and Zhou: Minimal Discrete
> > Energy
> > > > > on the Sphere,
> > > > > Mathematical Research Letters, Vol. 1 (1994),
> > pp.
> > > > > 647-662.
> > > > >www.math.vanderbilt.edu/~esaff/texts/155.pdf
>
> > > > > Best regards,
>
> > > > >KnudThomsen
> > > > > Geologist
>
> > > > So, you put a point at the south and north poles
> > and then space the otherpointsalong thespiralthat
> > connects the south and north poles. I have found
> > that it works out nicely if you space thepoints
> > along the sprial starting "half a step" from the
> > south pole and ending "half a step" from the north
> > distance (on the sphere) between turns of thespiral
> > equals (approximately) the distance betweenpoints
>
> > > > h(k) = -1 + (2*k - 1)/n, k = 1, 2, ..., n
> > > > phi(k) = arccos(h(k))
> > > > theta(k) = sqrt(n*pi)*phi(k)
>
> > > > I have not calculated the potential energy for
> > found it worked better than that of Rakhmanov, Saff,
> > and Zhou.
>
> > > > - MO- Hide quoted text -
>
> > > > - Show quoted text -
>
> > > Congratulations, Michael, the performance of your
>
> What I particularly like about Bauer's algorithm is that it is deterministic (is there a better word?) rather than iterative. Bauer also defines some nice measures of uniformity based on the Voronoi diagram.
>
> What does dE(-1,n), dE(0,n), and dE(+1,n) mean? I do not understand what the first argument represents.
>
>
> - Show quoted text -
First sorry about the late reply!
Correction: congratulations to Bob Bauer about his accomplishment and
thanks to Michael for making me aware of it!
Yes, the algorithm is not just being effective, it is beautifully
simple, too, the positioning of a particular point not depending on
that of its predecessor.
Michael, dE(s,n) is the improvement in potential energy (of type s)
obtained for our particular spiral over the one devised by Rakhmanov
et al., divided by the maximum possible such improvement, namely the
one provided by the theoretically optimal point configuration.
Regarding the definition of the energy types please see my original
posting:
http://groups.google.com/group/sci.math/browse_thread/thread/327a68f46940226e
Best regards,
Knud Thomsen
sa...@kt-algorithms.com
of Bauer and Rakmanov et al.
The similarity is really just below the surface.
Let us denote the longitude as phi.
1. Rakmanov et al.:
dphi(h)/dh = 3.6/sqrt(n)/r (n/2)
= 1.8 sqrt(n)/r
where the factor n/2 corrects for the non-infinitisimal step size.
2. Bauer:
dphi(h)/dh = sqrt(pi n) darccos(h)/dh
= sqrt(pi n)/sqrt(1-h^2)
= sqrt(pi n)/r
= 1.772(..) sqrt(n)/r
Best regards,
Knud Thomsen
sa...@kt-algorithms.com
pi in Bauer's longitude calculation with the corresponding (semi-
empirical) value (3.6/2)^2 = 3.24 from the spiral of Rakhmanov, Saff
and Zhou, we get slightly better potential energies. In particular I
like the fact that the convergence for n->infinity, which has worried
me a bit, looks better.
n dE(-1,n) dE( 0,n) dE(+1,n)
---------------------------------
4 1.029355 1.008939 0.984461
5 0.995598 0.983682 0.965456
6 1.013700 1.003542 0.983430
7 0.963860 0.961153 0.960249
8 0.978428 0.975673 0.973855
9 0.966625 0.964493 0.963916
10 0.934881 0.936988 0.943605
11 0.946011 0.945805 0.946071
12 0.958207 0.956867 0.954656
13 0.933802 0.935948 0.943261
14 0.917211 0.921943 0.937058
15 0.932295 0.936422 0.950096
16 0.940226 0.943116 0.953898
17 0.919972 0.925354 0.940490
20 0.915948 0.921589 0.933867
25 0.894147 0.905444 0.932603
30 0.863723 0.878911 0.910160
50 0.801400 0.830938 0.891700
100 0.716472 0.767679 0.865553
200 0.626588 0.702990 0.851920
500 0.391312 0.500397 0.767565
1000 0.247882 0.355191 0.699457
2000 0.148632 0.237709 0.629668
5000 0.070795 0.128808 0.534353
10000 0.038232 0.075659 0.455589
20000 0.019176 0.040852 0.365825
Best regards,
Knud Thomsen
Michael Orion
> substitute the constant
> pi in Bauer's longitude calculation with the
> corresponding (semi-
> empirical) value (3.6/2)^2 = 3.24 from the spiral of
> Rakhmanov, Saff
> and Zhou, we get slightly better potential energies.
> In particular I
> like the fact that the convergence for n->infinity,
> which has worried
> me a bit, looks better.
>
> n dE(-1,n) dE( 0,n) dE(+1,n)
> ---------------------------------
> 4 1.029355 1.008939 0.984461
> 5 0.995598 0.983682 0.965456
> 6 1.013700 1.003542 0.983430
> 10000 0.038232 0.075659 0.455589
> 20000 0.019176 0.040852 0.365825
>
> Best regards,
>
> Knud Thomsen
>
Not sure what you mean by "problems with convergence". Bauer's points showed slightly greater "p=-1" and "p=0" potential than RSZ's for n > 5000, but Bauer's potential certainly did not diverge. Also, Bauer's "p=1" potential was better even for n=10000.
Which brings out a good point to consider further. What is the best measure for the distribution of points? Many have used potential energy as a measure of uniformity of points on a sphere, lower energy implying better uniformity. But there are other measures. For example, consider the variance in the area of the Voronoi cells surrounding each point. Lower variance implies better uniformity. Or the difference between the max and min Voronoi area. Using a measure based on the Voronoi diagram represents a more localized measure. Only the closest points to a given point play a role in the measure.
Of course, which measure is best depends on what you plan to do with the points. So how do you plan to use the set of points that you generate?
One final point, if I recall correctly RSZ put a point at the south and north poles, whereas Bauer puts points half a step away from the poles. Not sure that this is any better. Just pointing out the difference.
- MO
sa...@kt-algorithms.com
>
> - Show quoted text -
Many thanks for your comments, Michael.
As pointed out earlier in this thread, I do not doubt that the Bauer
spiral converges; its convergence just seemed a bit slow considering
its impressive performance for even relatively big values of n.
The main reason for my using the energy measure here is that my
discussion started in the context of the RSZ spiral, which was
specifically designed by the authors to have a low potential energy.
One reason I'm interested in a good point spiral is that I have found
it to be a very valuable component in an algorithm that generates
approximately uniformly distributed points on the surface of a 4D unit
hypersphere (these points can then be utilized as appr. uniformly
distributed orientation/rotations). Using the spiral repeatedly this
way is an interesting alternative to (for example) the recursive zonal
equal area method devised by Paul Leopardi (1).
It's correct that the RSZ spiral puts a point at each pole and then
spaces the remaining points evenly in between. I actually started this
thread because the RSZ spiral could be improved considerably by
increasing the distance between the polar points and their immediate
neighbors.
1. Paul Leopardi, "A partition of the unit sphere into regions of
equal area and small diameter", Electronic Transactions on Numerical
Analysis, Volume 25, 2006, pp. 309-327.
Best regards,
Knud Thomsen
Michael Orion
Knud,
I am still not understanding what you mean by convergence. Could you try to explain more fully. You are comparing the energy of RSK to the energy of Bauer, seeing that Bauer's energy converges more slowly to RSK's than other algorithms and then are implying that Bauer's slow convergence to RSK is an undesirable trait.
Is convergence, fast or slow, to RSK a desirable feature?
Also, if what you want is uniformly distributed points, then I would indeed argue that that are better measures of uniformity than potential energy.
- MO
sa...@kt-algorithms.com
1. In my tables, I list: the difference in the energy of a particular
spiral from the optimum energy, as a fraction of the difference in the
energy of the original RSZ spiral from that same optimum energy.
More precisely, if
E(s,n) is the energy of original RSZ spiral
E'(s,n) is the energy of the particular spiral under discussion
(e.g. Bauer's spiral)
f(s,n) is the optimum energy, i.e. the energy of the optimal
point configuration, as approximated
in the RSZ paper.
then my table lists the value:
dE(s,n) = (E(s,n)-E'(s,n)) / (E(s,n)-f(s,n))
Consequently, we have the following special cases:
dE<0: The spiral under discussion is wose energy-wise than the RSZ
spiral
dE=0: The spiral under discussion has the same energy as the RSZ
spiral
dE=1: The spiral under discussion has the optimum energy.
2. I'm fully aware that there may be better criteria than potential
energy, depending on the exact application.
Best regards,
Knud Thomsen
sa...@kt-algorithms.com
approximately uniformly distributed points on the surface of a 4D
paper of his, where he describes a spiral on S4 (!!!):
Robert Bauer: Uniform Sampling of SO3. Presented at the Flight
Mechanics Symposium, 2001 June, Goddard Space Flight Center,
Greenbelt, Maryland.
Best regards,
Knud Thomsen