Re: Uniform sampling on the unit n-sphere... herrr... Not so uniform.
- From: Dave Seaman <dseaman@xxxxxxxxxxxx>
- Date: Wed, 13 Apr 2005 13:21:11 +0000 (UTC)
On 13 Apr 2005 06:03:50 -0700, jrfsousa@xxxxxxxxxxxx wrote:
> Hi!
> Thank you very much!
> I was quitte sure it was something dumb... And at least there was one
> thing I was not wrong about!
> Yes now I see that the distribution must be rotation invariant before
> the normalization or one will have "greatter density" zones and wrong
> results.
> Let me thank you again for your help and apologise to the group for
> wasting bandwith with dumb questions.
> Best regards
> José Rui
Here are four methods for generating uniformly distributed points on a unit
sphere:
(1) The normal-deviate method. Choose x, y, and z, each
normally distributed with mean 0 and variance 1. (Actually, the
variance does not matter, provided it remains fixed.) Normalize
the result to obtain a uniform density on the unit sphere.
This method also generalizes nicely to n dimensions. It works
because the vector chosen (before normalization) has a density
that depends only on the distance from the origin. The method is
mentioned in Knuth, _The Art of Computer Programming_, vol. 2,
3rd. ed., section 3.4.1.E.6.
(2) The hypercube rejection method. Choose x, y, and z, uniformly
distributed on [-1,1]. Compute s = x^2 + y^2 + z^2. If s > 1,
reject the triplet and start over. Once you have an acceptable
vector, normalize it to obtain a point on the unit sphere.
This method also generalizes to n dimensions, but as the dimension
increases the probability of rejection becomes high and many random
numbers are wasted.
(3) The trig method. This method works only in 3-space, but it is
very fast. It depends on the slightly counterintuitive fact (see
proof below) that each of the three coordinates of a uniformly
distributed point on S^2 is uniformly distributed on [-1,1] (but
the three are not independent, obviously). Therefore, it
suffices to choose one axis (Z, say) and generate a uniformly
distributed value on that axis. This constrains the chosen point
to lie on a circle parallel to the X-Y plane, and the obvious
trig method may be used to obtain the remaining coordinates.
(a) Choose z uniformly distributed in [-1,1].
(b) Choose t uniformly distributed on [0, 2*pi).
(c) Let r = sqrt(1-z^2).
(d) Let x = r * cos(t).
(e) Let y = r * sin(t).
(4) A variation of method (3) that doesn't use trig may be found in
Knuth, _loc. cit._. The method is equivalent to the following:
(a) Choose u and v uniformly distributed on [-1,1].
(b) Let s = u^2 + v^2.
(c) If s > 1, return to step (a).
(d) Let a = 2 * sqrt(1-s).
(e) The desired point is (a*u, a*v, 2*s-1).
This method uses two-dimensional rejection, which gives a higher
probability of acceptance compared to algorithm (2) in three
dimensions. I group this with the trig method because both
depend on the fact that the projection on any axis is uniformly
distributed on [-1,1], and therefore both methods are limited to
use on S^2.
--------------------------------------------------------------------
Here is a proof of correctness for the fact that the z-coordinate is
uniformly distributed. The proof also works for the x- and y-
coordinates, but note that this works only in 3-space.
The area of a surface of revolution in 3-space is given by
A = 2 * pi * int_a^b f(x) * sqrt(1 + [f'(x}]^2) dx
Consider a zone of a sphere of radius R. Since we are integrating in
the z direction, we have
f(z) = sqrt(R^2 - z^2)
f'(z) = -z / sqrt(R^2-z^2)
1 + [f'(z)]^2 = r^2 / (R^2-z^2)
A = 2 * pi * int_a^b sqrt(R^2-z^2) * R/sqrt(R^2-z^2) dz
= 2 * pi * R int_a^b dz
= 2 * pi * R * (b-a)
= 2 * pi * R * h,
where h = b-a is the vertical height of the zone. Notice how the integrand
reduces to a constant. The density is therefore uniform.
--
Dave Seaman
Judge Yohn's mistakes revealed in Mumia Abu-Jamal ruling.
<http://www.commoncouragepress.com/index.cfm?action=book&bookid=228>
.
- References:
- Prev by Date: Re: Uniform sampling on the unit n-sphere... herrr... Not so uniform.
- Next by Date: Re: Neumann BC implementation on 2d rectangular grid
- Previous by thread: Re: Uniform sampling on the unit n-sphere... herrr... Not so uniform.
- Index(es):
Relevant Pages
|
