
> 
> **Possible Duplicate:**  
> 
> [Efficiently sampling points uniformly from the surface of an n-sphere](https://mathoverflow.net/questions/24688/efficiently-sampling-points-uniformly-from-the-surface-of-an-n-sphere) 
> 
> 
> 


I'm trying to generate random points of a (n-2)-sphere on a n-hyperplane so basically the intersection of a (n-1)-sphere and a n-hyperplane.


The hyperplane here is the plane associated with a (n-1)-simplex of equation: $x\_1 + x\_2 + ... + x\_n = 1$


I know the radius $R$ of the n-sphere and I know the center $a$ which is in the simplex.
$a = (a\_1, a\_2, ..., a\_n)$ and $a\_1+a\_2+...+a\_3=1$


So the points I want to generate are solution of :


$x\_1 + x\_2 + ... + x\_n = 1$ and 
$(x\_1-a\_1)^2 + (x\_2-a\_2)^2 + ... + (x\_n-a\_n)^2 = R^2$


I absolutely need to generate points uniformly and in Cartesian coordinates. 


I have been looking into it for a few days now and cannot seem to find a good way to do it.


For the moment I did it on $\mathbb{R}^3$ which is equivalent to generate points of a circle on a plane. To do so, I projected the space on the 2-simplex (3D->2D) and I generated points of a circle using :


$(u,v) = \frac{R}{\sqrt{X\_1^2 + X\_2^2}}(X\_1,X\_2)$ where $X\_1, X\_2$ are independent gaussians.


(this algorithm allows you to generate points on a n-sphere too)


Finally, I used an "inverse-projection" of the simplex to the space (after some calculus...) :


$z = \sqrt{2/3} \cdot v $


$y = \frac{u}{\sqrt{2}} - 1/2 \cdot z$


$x=1-y-z$


Here is a graph to give you an exemple of what I just presented in 3 dimensions. The standard 2-simplex is the area represented in cyan.


<http://www.freeimagehosting.net/t/aksf6.jpg>
(sorry cannot post image tags...)


Of course, those formulas are easily derived in 3 dimensions but not as easily in $\mathbb{R}^n$.


I feel like I am looking at the problem the wrong way so any idea is welcome.


Thanks.



Generate points of a (n-2)-sphere on a n-hyperplane
I'll answer using matrix vector notation, which generalizes the problem to multiple linear constraints. We wish to generate a point $\mathbf{x}$ which is in the intersection of a hypersphere and an affine space, which we can write like this:


$$\|\mathbf{x}-\mathbf{x}\_0\|=r$$
$$\mathbf{Ax}=\mathbf{b}$$


Then we can generate $\mathbf{x}$ with this procedure:


$$\mathbf{z} \sim \mathcal{N}(\mathbf{0},\mathbf{I}) $$
$$\mathbf{z} := \mathbf{z} - \mathbf{A}^\dagger\mathbf{Az}$$
$$\mathbf{y} := \mathbf{A}^\dagger (\mathbf{b}-\mathbf{Ax}\_0)$$
$$\mathbf{x} := \mathbf{x}\_0 + \mathbf{y} + \frac{\mathbf{z}}{\|\mathbf{z}\|}(r - \|\mathbf{y}\|)$$


The idea here is that the point $\mathbf{x}\_0 + \mathbf{y}$ is the center of the intersection, and $\mathbf{z}/\|\mathbf{z}\|$ is uniformly distributed on the unit sphere of the null space of $\mathbf{A}$. 


Note, we must have $r \ge \|\mathbf{y}\|$, otherwise the intersection is empty. Also, we assume $\mathbf{A}$ is full rank so that the pseudoinverse satisfies $\mathbf{A}^\dagger = \mathbf{A}^T(\mathbf{A A}^T)^{-1}$. In your case $\mathbf{A} = \mathbf{1}^T$ so $\mathbf{A}^\dagger = n^{-1}\mathbf{1}$.


