CODEWITHSUNDEEP
mathrandomgeometryevolutionary-algorithm
Tomasz Nguyen
Tomasz Nguyen

Reputation: 2611

Generating random points on a surface of an n-dimensional torus

I'd like to generate random points being located on the surface of an n-dimensional torus. I have found formulas for how to generate the points on the surface of a 3-dimensional torus:

x = (c + a * cos(v)) * cos(u)
y = (c + a * cos(v)) * sin(u)
z = a * sin(v)

u, v ∈ [0, 2 * pi); c, a > 0.

My question is now: how to extend this formulas to n dimensions. Any help on the matter would be much appreciated.

Upvotes: 5

Views: 1806

Answers (3)

Peter O.
Peter O.

Reputation: 32898

Merely generating u and v uniformly will not necessarily sample uniformly from a torus surface. An additional step is needed.

J.F. Williamson, "Random selection of points distributed on curved surfaces", Physics in Medicine & Biology 32(10), 1987, describes a general method of choosing a uniformly random point on a parametric surface. It is an acceptance/rejection method that accepts or rejects each candidate point depending on its stretch factor (norm-of-gradient). To use this method for a parametric surface, several things have to be known about the surface, namely—

  • x(u, v), y(u, v) and z(u, v), which are functions that generate 3-dimensional coordinates from two dimensional coordinates u and v,

  • The ranges of u and v,

  • g(point), the norm of the gradient ("stretch factor") at each point on the surface, and

  • gmax, the maximum value of g for the entire surface.

For the 3-dimensional torus with the parameterization you give in your question, g and gmax are the following:

  • g(u, v) = a * (c + cos(v) * a).
  • gmax = a * (a + c).

The algorithm to generate a uniform random point on the surface of a 3-dimensional torus with torus radius c and tube radius a is then as follows (where RNDEXCRANGE(x,y) returns a number in [x,y) uniformly at random, and RNDRANGE(x,y) returns a number in [x,y] uniformly at random):

// Maximum stretch factor for torus
gmax = a * (a + c)
while true
 u = RNDEXCRANGE(0, pi * 2)
 v = RNDEXCRANGE(0, pi * 2)
 x = cos(u)*(c+cos(v)*a)
 y = sin(u)*(c+cos(v)*a)
 z = sin(v)*a
 // Norm of gradient (stretch factor)
 g = a*abs(c+cos(v)*a)
 if g >= RNDRANGE(0, gmax)
    // Accept the point
    return [x, y, z]
 end
end

If you have n-dimensional torus generating formulas, a similar approach can be used to generate uniform random points on that torus (accept a candidate point if norm-of-gradient equals or exceeds a random number in [0, gmax), where gmax is the maximum norm-of-gradient).

Upvotes: 0

Robert Dodier
Robert Dodier

Reputation: 17573

An n-torus (n being the dimensionality of the surface of the torus; a bagel or doughnut is therefore a 2-torus, not a 3-torus) is a smooth mapping of an n-rectangle. One way to approach this is to generate points on the rectangle and then map them onto the torus. Aside from the problem of figuring out how to map a rectangle onto a torus (I don't know it off-hand), there is the problem that the resulting distribution of points on the torus is not uniform even if the distribution of points is uniform on the rectangle. But there must be a way to adjust the distribution on the rectangle to make it uniform on the torus.

Upvotes: 0

MvG
MvG

Reputation: 60968

I guess that you can do this recursively. Start with a full orthonormal basis of your vector space, and let the current location be the origin. At each step, choose a point in the plane spanned by the first two coordinate vectors, i.e. take w1 = cos(t)*v1 + sin(t)*v2. Shift the other basis vectors, i.e. w2 = v3, w3 = v4, …. Also take a step from your current position in the direction w1, with the radius r1 chosen up front. When you only have a single basis vector remaining, then the current point is a point on the n-dimensional torus of the outermost recursive call.

Note that while the above may be used to choose points randomly, it won't choose them uniformly. That would likely be a much harder question, and you definitely should ask about the math of that on Math SE or perhaps on Cross Validated (Statistics SE) to get the math right before you worry about implementation.

Upvotes: 1

Related Questions