 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Math Forum / Mathematics / General Topics / February 2007'Generalized spiral points': further improvement
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) 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 > In a recent posting (1) I proposed a slight > adjustment to the [quoted text clipped - 152 lines] > 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. - MO > > In a recent posting (1) I proposed a slight > > adjustment to the [quoted text clipped - 164 lines] > > - 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 On Feb 26, 10:16 am, "s...@kt-algorithms.com" <s...@kt-algorithms.com> wrote: > > > In a recent posting (1) I proposed a slight > > > adjustment to the [quoted text clipped - 205 lines] > > - 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 > On Feb 26, 10:16 am, "s...@kt-algorithms.com" > <s...@kt-algorithms.com> [quoted text clipped - 263 lines] > > 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. - MO > > On Feb 26, 10:16 am, "s...@kt-algorithms.com" > > <s...@kt-algorithms.com> [quoted text clipped - 277 lines] > > - 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 Below is an informal comparison of the spiral longitude calculations 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 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 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 > If we, in accordance with my previous posting, > substitute the constant [quoted text clipped - 20 lines] > > 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 > > If we, in accordance with my previous posting, > > substitute the constant [quoted text clipped - 32 lines] > > - 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 > On Feb 28, 7:23 pm, Michael Orion > <beewo...@hotmail.com> wrote: [quoted text clipped - 110 lines] > > 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. - MO > > On Feb 28, 7:23 pm, Michael Orion > > <beewo...@hotmail.com> wrote: [quoted text clipped - 122 lines] > > - 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. Best regards, Knud Thomsen 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. Best regards, Knud Thomsen |
Reply to this Message |
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2012 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.