Comment by DoctorOetker | Hacker News Reader

Comment by DoctorOetker | Hacker News Reader

Parent Full thread

While your R2 sequence is obviously better than the others for hyper uniform distribution on the sphere, I can't help but notice there are still spiral patterns. (are we looking at a pole of the coordinate transform btw?).

Is this fundamentally the same or similar problem as the rectangular stretch mentioned here? But with a "jacobian" stretch as opposed to a linear stretch?

Could you please read the short section https://en.wikipedia.org/wiki/Orthogonal_matrix#Randomizatio... ?

It is very short, first it defines what is meant with a random orthogonal matrix, then it describes the problem with an incorrect approach, ... and then it describes a recursive procedure to generate a random orthogonal matrix of dimension D using D * (D+1) / 2 uniformly distributed numbers:

>Stewart (1980) replaced this with a more efficient idea that Diaconis & Shahshahani (1987) later generalized as the "subgroup algorithm" (in which form it works just as well for permutations and rotations). To generate an (n + 1) × (n + 1) orthogonal matrix, take an n × n one and a uniformly distributed unit vector of dimension n + 1. Construct a Householder reflection from the vector, then apply it to the smaller matrix (embedded in the larger size with a 1 at the bottom right corner).

I predict this will give a better uniform distribution on that sphere, if you share your code for generation and visualization I might try myself :)

Also, I applaud you for the extremely clear exposition of the problem, thought process and analogies presented. The one section I found harder to grasp was the one on dithering, as I don't fully understand the process from input picture to output pixel locations and intensities...

Thank you for your kind words! Regarding the mapping of R_2 to the surface of the sphere, I totally agree that although it is better than other options, it is far from optimal. Also, yes, these visualizations are looking from the North pole downwards as I thought this viewpoint highlighted the differnces and discrepancies the best. It was this clearly suboptimal mapping that spurred me to write a prior blog post on improved ways to place N points on a sphere [1].

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.

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

And finally regarding the section on dithering. Thanks for the feedback. I will add some more background explanations to ensure that it is clearer for those who do not directly work in the graphics rendering space.

[1] http://extremelearning.com.au/evenly-distributing-points-on-... [2] http://www.math.vanderbilt.edu/saffeb/texts/262.pdf

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.

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

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

Reply on news.ycombinator.com