Hacker News Reader

>I think that much of the problem is not with the particular unit square point distribution but rather with the fact that we are using a mapping (lambert) that has a singularity at each pole.

I agree that the mapping is causing the remaining issue, and that the singularity is emphasizing it, but I think it is any stretching of a mapping that is causing the spiral clustering towards the equator.

>For constant/given n, there is an excellent reference by Saff on mapping points to a sphere. However, if n is not known (ie you need an open sequence of points) I am not aware of any method that is better than simply/naively mapping a low discrepancy sequence from the unit square to S2.

I understand the advantage of your R2 method regarding open sequences, and the quasi-magical property you can use it to just keep appending points to the collection without any need to "remember" the points already added to position the fresh point. This is clearly a desirable property.

>I think that the most ideal situation will work directly on the surface of the sphere and consist of rotations from one point on the surface to the other. Thus, although this is not my area of expertise I wouldn't be surprised if methods such as what you cite may assist someone in finding a better spherical distribution.

It seems you misunderstood me thinking I was proposing an alternative to an R_2 based method. On re-reading my comment I see I should have been clearer on what I was proposinng:

I proposed using R_2 for a sequency of 6-dimensional tuples (or perhaps just 5-dimensional if the first random number should be 1). Each tuple generated by your R_2 would be used to construct the 3 dimensional random rotation matrix as described. Each rotation matrix then rotates the same reference point (0,0,1). I was proposing an alternative to the lambert mapping, but still using your R_2 sequence, so you keep having an open sequence of points.

I believe you have discovered something very fundamental here, and I can identify with the person who asked for the 1x2 rectangle: perhaps by modifying R_2 for enough simple variations on the problem we can generalize to arbitrary shapes, manifolds or metrics. I am unsure what the best approach is: modify the core logic for generating the next 2-dimensional point in 1x2 rectangle such that it remains hyper-uniform or treat the R_2 sequence as the fundamental primitive, and generate higher dimensional tuples for the uniform hyper-cube and then use math to somehow project it to 2 dimensions.

Thanks for sharing your insights!

1. Stretching I think you and Jacob are on to something when we realise that the R_2 sequence (and presumably R_D) loses some of its properties when it is naively stretched. I think if we solve this problem then we can make some real progress in the sphere problem.

2. Regarding rotations. Yes, I agree. When i wrote 'rotations' i meant it very generally. Any direct transformations from one point on the sphere to another without requiring intermediate mappings such as on a Torus.

3. 6-tuples. This is a really interesting idea, and sorry I missed it the first time. I will definitely explore this idea more.

regarding the nr 1: the reason I'd prefer solving the rectangular version first is because I see 2 potential sources of problem: on one hand an anisotropic but still flat metric (i.e. no curvature) and on the other hand the shape or topology of spaces like sphere (which admits elliptic metrics) or double torus (hyperbolic geometry) which force curvature on the metric. That the problem arises already for a flat metric is why I think it deserves attention.

Although the problem can be seen with visual inspection, it incurs some effort to inspect. I propose the following visualization: after generating say N=1000 points, for each point select the closest neighbour, and plot its distance with respect to the origin, then ideally one would get a circular band centered on the origin. Alternatively, plot the angle for each nearest neighbour vector and ideally one should see a uniform distribution.

It's unclear which part(s) need to be generalized for the rectangular version: the equation for the phi's? some rescaling of the phi's? the update rule itself? or some function on the output of the update rule?

Another approach may be to change the concept of hyper uniformity and generalize it to "hyper convergence of [arbitrary function]" i.e. can we have fast convergence to a hat or tent function? If we take the 2-dimensional R_2 and compute the sum of the pair of pseudo-independent numbers, does it generate a tent function? still faster than random sequence? Instead of looking at the distance between adjacent points for the non-uniform tent function, we might multiply this distance by the distance to 0 or 2 (whichever is closest). I.e. points near the floor (0 or 2) should be further apart but will have a lower multiplier since its close to 0 or 2, while points near the top of the tent function (1) will have small distances between them but a higher distance fromm 0 or 2.

For a couple of moments I incorrectly conjectured that spaces have "magic geodesic steps" i.e. for a torus moving straight up or straight to the right does not create a dense point set on the unit square, while the R_2 step does. The reason I think there is no general "magic geodesic step" or at least that it is less related to geodesics as I thought is because every geodesic on the unit sphere turns back on itself.

I am also interested in points on the sphere.

I was thinking about using a projection based on mapping a square to an octahedron (along the general pattern of the “quincuncial projection”, but perhaps preserving areas).

However, the topology on the square is not a torus formed by associating opposite sides (as in your pattern) but instead has the two halves of each side of the square folded onto each-other. I suspect the points in the sequence won’t be quite as well distributed near those seams.

> rotations from one point on the surface to the other

This is an interesting idea. You might want to keep track of the previous rotation, rather than just the previous point. You could do some kind of search over the space of unit quaternions to find ones which effectively distributed points.