'Generalized spiral points': a slight adjustment

213 views
Skip to first unread message

sa...@kt-algorithms.com

unread,
Feb 6, 2007, 7:27:42 AM2/6/07
to
In 1994 Rakhmanov, Saff and Zhou (1) suggested a simple and elegant
spiral set of n points on the surface of the unit sphere, which for
increasing n has a total 'potential energy' that converges nicely to
the global extremum value for n 'evenly distributed' points on the
sphere.

It seems that the small modification of the spiral algorithm suggested
below leads to a slight improvement in the potential energy.

We shall restrict ourselves to three types of potential energy E(s,n)
which are discussed in detail by the above authors:

E(-1,n) = sum(n>=j>i>=1) 1/dij
E( 0,n) = sum(n>=j>i>=1) ln(1/dij)
E(+1,n) = sum(n>=j>i>=1) -dij

dij being the Euclidean distance between points i and j.
Note that in this discussion the sign of E(+1,n) is chosen so that the
global extremum is a minimum, as for the other two.

The spiral point set of Rakhmanov et al. can be defined, in spherical
coordinates (pi>=theta>=0, 2pi>=phi>=0) and for point index 1<=k<=n:

h(k) = -1 + 2(k-1)/(n-1)
theta(k) = arccos(h(k))
r(k) = sqrt(1-h(k)^2)
0, k=1
phi(k) = [phi(k-1) + 3.6/sqrt(n) 1/r(k)] (mod 2pi), 2<k<n-1
0, k=n

Note that the horizontal radius r(k) is used to define the increment
in phi from point k-1 to point k.

An interesting idea is to use instead a kind of midway radius in the
calculation of that phi increment, namely (r(k-1)+r(k))/2, and this
actually results in a small decrease in the potential energy.

Let us denote the energies measured for Rakhmanov et al.'s original
algorithm as E(s,n), and those measured for the suggested modification
as E'(s,n).
Fortunately, the authors also created good approximations to the
minimum energy for n points, here denoted f(s,n), and we shall use
these approximations to estimate the fractional improvement towards
the minimum energy:

dE(s,n) = (E(s,n)-E'(s,n)) / (E(s,n)-f(s,n))

The table below gives the fractional improvement for selected n:

n dE(-1,n) dE( 0,n) dE(+1,n)
---------------------------------
2 -0.000000 -0.000000 -0.000000
3 0.000000 0.000000 0.000000
4 0.000000 -0.000000 0.000000
5 0.002477 -0.000791 -0.008293
6 0.018490 0.025285 0.046053
7 0.035677 0.054766 0.110411
8 0.043506 0.062189 0.109718
9 0.048726 0.060885 0.083121
10 0.044847 0.051442 0.053930
20 0.066426 0.070708 0.068975
50 0.065120 0.067782 0.073075
100 0.064206 0.061789 0.049650
200 0.056133 0.052754 0.036536
500 0.034383 0.033912 0.024079
1000 0.021504 0.022263 0.015808
2000 0.012785 0.013871 0.010400
5000 0.006038 0.006875 0.005531
10000 0.003248 0.003796 0.003402
20000 0.001626 0.001934 0.001959

1. 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

sa...@kt-algorithms.com

unread,
Feb 6, 2007, 7:42:06 AM2/6/07
to
In the definition of phi(k), please read 2<=k<=n-1 rather than
2<k<n-1.

Knud Thomsen


Reply all
Reply to author
Forward
0 new messages