Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to generate uniformly random points on n-spheres and in n-balls

extremelearning.com.au

Post reply on HN
Print view View original

71–80 of 87 posts

Re: How to generate uniformly random points on n-spheres and in n-balls

#71

Post by Certhas »

throwaway81523 wrote: post #54
ianferrel wrote: post #45

Earlier quoted context omitted.

Sure, but for the most-used real-world geometry, n = 2 or 3. So how fast it grows really doesn't matter. Most maps are 2-dimensional and this is fine.

When I saw "n" in the title I assumed they wanted something that worked reasonably for large n. Rejection is no good because of the notorious "curse of dimensionality". So my idea was to choose a suitable distribution on the radius, then draw from it and choose the angles at random (not sure what those angles are called). You might have to delete the point at the center for that to work.

The article explicitly discusses both. Versions for low dimensions that have favorable properties, and those for high dimensions.

The method you propose is not used in high dimensions in practice as it would involve evaluating order n^2 trigonometric functions and is also far harder to implement than the methods discussed in the article.

Re: How to generate uniformly random points on n-spheres and in n-balls

#72

Post by longhaul »

frankfrank13 wrote: post #6

I actually needed this at work once! We needed to fuzz peoples address in a mapped view for analytics, without revealing PII. It ended up never being shipped, but we needed to fuzz geographic data and the thinking was like: 1. Truncate your lat longs to some arbitrary decimal place (this is very very stupid, you end up with grid lines [1]) 2. The above method ^^ but everyone tries basically doing like random angle +…

Long time ago, I had the same problem while ray tracing using Monte Carlo techniques. Using Mersenne Twister fixed the clustering and grid like randomization. https://en.m.wikipedia.org/wiki/Mersenne_Twister

Re: How to generate uniformly random points on n-spheres and in n-balls

#73

Post by frumiousirc »

stefanka wrote: post #65

I encountered the need for uniform random points on hyperspheres, and found this solution (with Python code) very helpful: https://stackoverflow.com/a/59279721 . Currently, I am porting my codebase to Rust and did that part over the weekend, so if anyone is interested in this exact implementation, I'd willing to share it (as a crate if necessary).

The linked SO question is not about uniform random points. The poster explicitly excludes answers involving uniform random distribution on a hypersphere.

Re: How to generate uniformly random points on n-spheres and in n-balls

#74

Post by xanderlewis »

eli_gottlieb wrote: post #49
xanderlewis wrote: post #34

Earlier quoted context omitted.

> simply choosing a random theta in 0,2pi and phi in -pi,pi, which ends up with points biased towards the poles. Am I right in thinking that it’s because circles of constant theta on the sphere contain the same ‘expected’ number of points (since phi is uniformly distributed), and these circles get smaller (and in the limit, shrink to a point) as one travels towards the poles — hence, higher density of points…? …makes…

> whilst the mapping (theta, phi) —> (x, y, z) is continuous, it isn’t uniformly so… or something like that. The term is "measure preserving". The mapping is continuous but it doesn't preserve the length of intervals projected through it.

Yes. That seems close to what I was looking for. Thanks.

Re: How to generate uniformly random points on n-spheres and in n-balls

#75

Post by alanbernstein »

fjkdlsjflkds wrote: post #70
alanbernstein wrote: post #64

Earlier quoted context omitted.

Force directed layout is my favorite for this.

...but then the algorithmic complexity goes from O(N) to O(N^2), or at least O(N log N), since points have to interact with each other. (N denotes the number of points you need to generate)

I confess I've never used this in a situation where time complexity was at all relevant. For one thing, it is possible that a result only needs to be computed once for each N (and per shape, since this approach works on a wider range of shapes than just spheres).

Re: How to generate uniformly random points on n-spheres and in n-balls

#77

Post by bagels »

alanbernstein wrote: post #64
bagels wrote: post #8

Earlier quoted context omitted.

I needed something related, n roughly evenly distributed points on the surface of a sphere. Ended up using a Fibonacci spiral. https://extremelearning.com.au/how-to-evenly-distribute-poin...

Force directed layout is my favorite for this.

Neat. My n was on the order of thousands, so that would have taken a while, but it could have been cached.

Re: How to generate uniformly random points on n-spheres and in n-balls

#78

Post by bee_rider »

fjkdlsjflkds wrote: post #69
contravariant wrote: post #38

Earlier quoted context omitted.

Fail is an understatement, the ratio between the two volumes is basically (n/2)!(4/pi)^(n/2). Which is also the expected number of tries you'll need. The time doesn't merely grow exponentially it grows faster than exponential. I don't actually know of any useful algorithms with worse asymptomatic behaviour.

> I don't actually know of any useful algorithms with worse asymptomatic behaviour. Note: "asymptomatic" does not mean the same as "asymptotic"

Most of my code has bad asymptomatic bugs but they never show up in testing because the tests don’t have data sets big enough to show the symptoms!

Re: How to generate uniformly random points on n-spheres and in n-balls

#79

Post by pugworthy »

xanderlewis wrote: post #42
pugworthy wrote: post #41

2-ball (disk) distribution is kind of interesting in gaming when simulating gun projectile hit locations. If the circle represents the area in which a simulated projectile will hit, you probably don't want a truly random distribution of points but instead have a bias towards the middle of the circle. A real gun shot multiple times at a fixed target will probably (assuming perfect aim but some variation on every shot)…

> truly random distribution > purely random distribution Nitpick: you don’t mean random ; you mean uniform .

Game players live and die (virtually) by the fabled RNG and pray to RNGesus even. So though mathematically uniform is the right word, gamer-wise, random is a pretty good word to use.

Re: How to generate uniformly random points on n-spheres and in n-balls

#80

Post by porphyra »

kurlberg wrote: post #68
porphyra wrote: post #52

Another way to generate uniformly random points on a 2D disk that the author forgot to mention: let A be an n x n complex matrix whose elements are iid copies of a fixed random variable with unit variance. Let lambda_i be its ith eigenvalue, and let x_i = 1/sqrt(n) real(lambda_i) and y_i = 1/sqrt(n) imag(lambda_i). As n approaches infinity, the distribution of x, y approaches almost certainly to the uniform distribut…

It's very inefficient, both on terms of runtime and in terms wasted entropy.

Indeed, haha.
Post reply on HN