1053 views

Skip to first unread message

Feb 25, 2007, 3:43:16â€¯AM2/25/07

to

In a recent posting (1) I proposed a slight adjustment to the

'generalized spiral points' procedure by Rakhmanov, Saff and Zhou (2).

'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

Feb 25, 2007, 4:09:22â€¯PM2/25/07

to

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

Feb 26, 2007, 4:16:42â€¯AM2/26/07

to

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

Feb 26, 2007, 4:38:41â€¯AM2/26/07

to

On Feb 26, 10:16 am, "s...@kt-algorithms.com" <s...@kt-algorithms.com>

wrote:> KnudThomsen- Hide quoted text -

>

> - Show quoted text -

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

Feb 26, 2007, 6:55:39â€¯AM2/26/07

to

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

Feb 27, 2007, 4:19:21â€¯AM2/27/07

to

On Feb 26, 12:55 pm, Michael Orion <beewo...@hotmail.com> wrote:

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

> > > > > 'generalizedspiralpoints' procedure by> > 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.

>

> - MO- Hide quoted text -

>

> - Show quoted text -

>

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

Feb 28, 2007, 4:10:11â€¯AM2/28/07

to

Below is an informal comparison of the spiral longitude calculations

of Bauer and Rakmanov et al.

The similarity is really just below the surface.

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

Feb 28, 2007, 10:03:29â€¯AM2/28/07

to

If we, in accordance with my previous posting, 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.

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

Feb 28, 2007, 1:23:21â€¯PM2/28/07

to

> If we, in accordance with my previous posting,

> 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

> snip> 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

Feb 28, 2007, 3:19:07â€¯PM2/28/07

to

> - MO- Hide quoted text -

>

> - Show quoted text -

>

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

Feb 28, 2007, 3:44:51â€¯PM2/28/07

to

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

Feb 28, 2007, 4:27:32â€¯PM2/28/07

to

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

Feb 28, 2007, 4:51:06â€¯PM2/28/07

to

Shortly after my mentioning in this thread the usefulness of

approximately uniformly distributed points on the surface of a 4D

hypersphere, Bob Bauer kindly informed me about another interesting

paper of his, where he describes a spiral on S4 (!!!):

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu