Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's say I have two n-spheres and I've no prior knowledge about the spheres (such as one of the sphere might be inside the other one) and I need to compute the volume of the intersection of the two hyper-spheres. Is there an efficient and generic way to compute the hyper-spherical cap of the intersection of these n-spheres? Note that the hyperspheres are expected to be very high dimensional such as 4096.

share|improve this question
2  
You'll need beta functions apparently. –  anon Jun 24 '12 at 3:43

2 Answers 2

up vote 6 down vote accepted

Let's suppose you are given the coordinates of the center and radius of each sphere. Then you can compute the distance between their centers.

The volume of the intersection depends only on this distance $d$ and the two radii $r_1$, $r_2$.

If $d \ge r_1+r_2$ then the sphere interiors do not intersect and the volume is zero.

If $d \le |r_1-r_2|$, then one sphere is inside the other and the volume is that of the smaller sphere.

Otherwise, the volume consists of two spherical caps, glued at a hyperplane.
The cap sizes can be found by considering the triangle with sides $r_1$, $r_2$, $d$, which appears on any planar cross-section including the line through the centers. The altitude to side $d$ is where the two caps are glued. The cap base heights are at the (signed) distances from the endpoints of side $d$ to this altitude: $$c_1 = \frac{d^2+r_1^2-r_2^2}{2d}$$ $$c_2 = \frac{d^2-r_1^2+r_2^2}{2d}$$

Now we just need to compute the cap volumes. EDIT: This cannot be done using elementary functions. The volume of a spherical cap can be expressed in terms of the gamma function $\Gamma$ and the regularized incomplete beta function $I$. For a clean derivation, see Concise Formulas for the Area and Volume of a Hyperspherical Cap, Shengqiao Li, Asian Journal of Mathematics and Statistics 4(1), 66-70, 2011.

$$ V^{cap}_n(r,a \ge 0) = \frac{1}{2} \frac{\pi^{n/2}}{\Gamma(\frac{n}{2}+1)}r^n I_{1-a^2/r^2}(\frac{n+1}{2},\frac{1}{2}) $$ $$ V^{cap}_n(r,a < 0) = \frac{\pi^{n/2}}{\Gamma(\frac{n}{2}+1)}r^n - V^{cap}_n(r,-a) $$

The final answer is then $V^{cap}_n(r_1,c_1)+V^{cap}_n(r_2,c_2)$.

share|improve this answer
    
thanks very clean explanation. –  mathemagician Jun 26 '12 at 1:03
1  
I know that this is an old answer but just for the sake of trying to improve it. I agree with @kirilsolo. The idea of this procedure is right, nevertheless the last integrand is mitaken. This is beacause the radius of the $(n-1)$-dimensional ball that we want to integrate is not x but rather a function of x, namely $(\sqrt{r_1^2-x^2})$ for the first ball and $(\sqrt{r_2^2-(x-d)^2})$. –  Bruce Wayne Nov 6 '13 at 14:55
2  
for the second one. The integral for the first ball then becomes $\int_a^rV_{n-1}((\sqrt{r_1^2-x^2})) dx$. Which can be expressed in some horrible formula using the hypergeometric function. –  Bruce Wayne Nov 6 '13 at 15:02
    
@Bruce Thank you for your comment, I have fixed the formula. –  Matt Nov 14 '13 at 17:43

It seems to me that the answer written above by Matt is incorrect. Specifically, the expression that is believed to be the exact value of $V_n^{cap}(r,a)$ is in fact only an underestimation which gets farther from the correct value as $n$ is increased. Formally the radius of $V_n^{cap}$ for a specific $x$ should be $$\sqrt{r^2-(r-x)^2}=\sqrt{2rx-x^2},$$ instead of just $x$.

Thus, the integral for this expression should look as follows $$V_n^{cap}(r,a)=\int_a^r V_{n-1}\left(\sqrt{2rx-x^2}\right)dx,$$ although I'm not sure how it can integrated.

share|improve this answer
    
Thank you for pointing this out (although I unfortunately didn't see your remarks until the system notified me of Bruce Wayne's comment on my answer). I have fixed the solution, and included a link to a paper that shows how to do the required integration. –  Matt Nov 14 '13 at 17:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.