In a recent posting (1) I proposed a slight adjustment to the '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:
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:
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
> In a recent posting (1) I proposed a slight > adjustment to the > '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:
> 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:
> 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
> 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.
> 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
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.
> > In a recent posting (1) I proposed a slight > > adjustment to the > > '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)
> > 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:
> > 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
> > 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.
> > 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:
> 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- Hide quoted text -
> - 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!
> On Feb 25, 10:09 pm, Michael Orion <beewo...@hotmail.com> wrote:
> > > In a recent posting (1) I proposed a slight > > > adjustment to the > > > '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)
> > > 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:
> > > 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
> > > 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.
> > > 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:
> > 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- Hide quoted text -
> > - 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!
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.
> 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 > > > > '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)
> > > > 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:
> > > > 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:
> > > > 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.
> > > > 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:
> > > 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- Hide quoted text -
> > > - 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!
> 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
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.
> > 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 > > Rakhmanov, > > > > > Saff and Zhou (2).
> > > > > For n>3, thespiralcan be further improved in > > terms > > > > > of its potential > > > > > energy by ensuring a greater spacing between > > the two > > > > > polarpointsand > > > > > their immediate neighbors, and then squeezing > > the > > > > > remainingpoints > > > > > 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)
> > > > > 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:
> > > > > 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:
> > > > > 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.
> > > > > 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 > > pole. The slope of thespiralis set so that the > > distance (on the sphere) between turns of thespiral > > equals (approximately) the distance betweenpoints > > along thespiral. To wit:
> > > > I have not calculated the potential energy for > > this set ofpoints, but using some ad hoc measures I > > found it worked better than that of Rakhmanov, Saff, > > and Zhou.
> > > > - MO- Hide quoted text -
> > > > - Show quoted text -
> > > Congratulations, Michael, the performance of your > >spiralis 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!
> > 1. For n=4, one may get the impression that Michael's > >spiralpoints > > 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
> Knud,
> Glad you liked the algorithm, but I must credit to
> Bauer, Robert, "Distribution ofPointson 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- Hide 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
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.
> 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.
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.
> > 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.
> 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- Hide 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.
> On Feb 28, 7:23 pm, Michael Orion > <beewo...@hotmail.com> wrote: > > > 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.
> > 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 > r n=10000.
> > Which brings out a good point to consider further. > What is the best measure for the distribution of > f 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- Hide 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
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.
> > On Feb 28, 7:23 pm, Michael Orion > > <beewo...@hotmail.com> wrote: > > > > 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.
> > > 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 > > r n=10000.
> > > Which brings out a good point to consider further. > > What is the best measure for the distribution of > > f 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- Hide 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,
> >KnudThomsen
> 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- Hide quoted text -
> - Show quoted text -
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.
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 (!!!):
Robert Bauer: Uniform Sampling of SO3. Presented at the Flight Mechanics Symposium, 2001 June, Goddard Space Flight Center, Greenbelt, Maryland.
|
