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.

I need to find the volume of the region defined by $$\begin{align*} a^2+b^2+c^2+d^2&\leq1,\\ a^2+b^2+c^2+e^2&\leq1,\\ a^2+b^2+d^2+e^2&\leq1,\\ a^2+c^2+d^2+e^2&\leq1 &\text{ and }\\ b^2+c^2+d^2+e^2&\leq1. \end{align*}$$ I don't necessarily need a full solution but any starting points would be very useful.

share|improve this question
1  
Nice problem. The only problem of this type that I have seen is the old calculus puzzle (that doesn't quite require calculus) of finding the volume of intersection of cylinders. There are nice solutions for $2$ cylinders, and even $3$. –  André Nicolas Jul 12 '11 at 0:35
    
A starting point would be finding the boundary. Any 2 hypercones positioned exactly on the axes (direction vectors $e_i$, $e_j$) will have two hyperplanes of intersection, their normal vectors being $e_i + e_j$ and $e_i-e_j$. Our resulting figure will thus have $2{5 \choose 2} = 20$ intersecting hyperplanes. All 5-hypercone intersections determine the vertices of a 5D hypercube, which has 10 different 4-cells, each cell showing 8 (no. of 3-cells on a 4D cube) pieces of curved surface, each piece shown on 2 4-cells, hence 10(8)/2 = 40 disjoint curved hypersurfaces of the figure. Good luck, lol. –  anon Jul 12 '11 at 1:18
    
I mean hypercylinder, not hypercone. My brain switched them for whatever reason. –  anon Jul 12 '11 at 2:31
1  
One might ask if there is a general formula for the volume of $n$ intersecting cylinders in $\mathbb{R}^n$, centered on the coordinate axes and having unit radius. Asymptotics as $n \to \infty$ could also be interesting. –  Nate Eldredge Jul 14 '11 at 14:21
    
@Nate: Funny you should say that just now -- I was just adding something about that to my answer :-) –  joriki Jul 14 '11 at 16:21

4 Answers 4

up vote 44 down vote accepted
+50

It turns out that this is much easier to do in hyperspherical coordinates. I'll deviate somewhat from convention by swapping the sines and cosines of the angles in order to get a more pleasant integration region, so the relationship between my coordinates and the Cartesian coordinates is

$$ \begin{eqnarray} a &=& r \sin \phi_1\\ b &=& r \cos \phi_1 \sin \phi_2\\ c &=& r \cos \phi_1 \cos \phi_2 \sin \phi_3\\ d &=& r \cos \phi_1 \cos \phi_2 \cos \phi_3 \sin \phi_4\\ e &=& r \cos \phi_1 \cos \phi_2 \cos \phi_3 \cos \phi_4\;, \end{eqnarray} $$

and the Jacobian determinant is $r^4\cos^3\phi_1\cos^2\phi_2\cos\phi_3$. As stated in my other answer, we can impose positivity and a certain ordering on the Cartesian coordinates by symmetry, so the desired volume is $2^55!$ times the volume for positive Cartesian coordinates with $a\le b\le c\le d\le e$. This translates into the constraints $0 \le \phi_4\le \pi/4$ and $0\le\sin\phi_i\le\cos\phi_i\sin\phi_{i+1}$ for $i=1,2,3$, and the latter becomes $0\le\phi_i\le\arctan\sin\phi_{i+1}$. The boundary of the volume also takes a simple form: Because of the ordering of the coordinates, the only relevant constraint is $b^2+c^2+d^2+e^2\le1$, and this becomes $r^2\cos^2\phi_1\le1$, so $0\le r\le\sec\phi_1$. Then the volume can readily be evaluated with a little help from our electronic friends:

$$ \begin{eqnarray} V_5 &=& 2^55!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_4}\int_0^{\arctan\sin\phi_3}\int_0^{\arctan\sin\phi_2}\int_0^{\sec\phi_1}r^4\cos^3\phi_1\cos^2\phi_2\cos\phi_3\mathrm dr\mathrm d\phi_1\mathrm d\phi_2\mathrm d\phi_3\mathrm d\phi_4 \\ &=& 2^55!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_4}\int_0^{\arctan\sin\phi_3}\int_0^{\arctan\sin\phi_2}\frac15\sec^2\phi_1\cos^2\phi_2\cos\phi_3\mathrm d\phi_1\mathrm d\phi_2\mathrm d\phi_3\mathrm d\phi_4 \\ &=& 2^55!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_4}\int_0^{\arctan\sin\phi_3}\frac15\sin\phi_2\cos^2\phi_2\cos\phi_3\mathrm d\phi_2\mathrm d\phi_3\mathrm d\phi_4 \\ &=& 2^55!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_4}\left[-\frac1{15}\cos^3\phi_2\right]_0^{\arctan\sin\phi_3}\cos\phi_3\mathrm d\phi_3\mathrm d\phi_4 \\ &=& 2^55!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_4}\frac1{15}\left(1-\left(1+\sin^2\phi_3\right)^{-3/2}\right)\cos\phi_3\mathrm d\phi_3\mathrm d\phi_4 \\ &=& 2^55!\int_0^{\pi/4}\left[\frac1{15}\left(1-\left(1+\sin^2\phi_3\right)^{-1/2}\right)\sin\phi_3\right]_0^{\arctan\sin\phi_4}\mathrm d\phi_4 \\ &=& 2^55!\int_0^{\pi/4}\frac1{15}\left(\left(1+\sin^2\phi_4\right)^{-1/2}-\left(1+2\sin^2\phi_4\right)^{-1/2}\right)\sin\phi_4\mathrm d\phi_4 \\ &=& 2^55!\left[\frac1{15}\left(\frac1{\sqrt2}\arctan\frac{\sqrt2\cos\phi_4}{\sqrt{1+2\sin^2\phi_4}}-\arctan\frac{\cos \phi_4}{\sqrt{1+\sin^2\phi_4}}\right)\right]_0^{\pi/4} \\ &=& 2^8\left(\frac1{\sqrt2}\arctan\frac1{\sqrt2}-\arctan\frac1{\sqrt3}-\frac1{\sqrt2}\arctan\sqrt2+\arctan1\right) \\ &=& 2^8\left(\frac\pi{12}+\frac{\mathrm{arccot}\sqrt2-\arctan\sqrt2}{\sqrt2}\right) \\ &\approx& 5.5035\;, \end{eqnarray} $$

which is consistent with my numerical results.

The same approach readily yields the volume in four dimensions:

$$ \begin{eqnarray} V_4 &=& 2^44!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_3}\int_0^{\arctan\sin\phi_2}\int_0^{\sec\phi_1}r^3\cos^2\phi_1\cos\phi_2\mathrm dr\mathrm d\phi_1\mathrm d\phi_2\mathrm d\phi_3 \\ &=& 2^44!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_3}\int_0^{\arctan\sin\phi_2}\frac14\sec^2\phi_1\cos\phi_2\mathrm d\phi_1\mathrm d\phi_2\mathrm d\phi_3 \\ &=& 2^44!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_3}\frac14\sin\phi_2\cos\phi_2\mathrm d\phi_2\mathrm d\phi_3 \\ &=& 2^44!\int_0^{\pi/4}\left[\frac18\sin^2\phi_2\right]_0^{\arctan\sin\phi_3}\mathrm d\phi_3 \\ &=& 2^44!\int_0^{\pi/4}\frac18\frac{\sin^2\phi_3}{1+\sin^2\phi_3}\mathrm d\phi_3 \\ &=& 2^44!\left[\frac18\left(\phi_3-\frac1{\sqrt2}\arctan\left(\sqrt2\tan\phi_3\right)\right)\right]_0^{\pi/4} \\ &=& 12\left(\pi-2\sqrt2\arctan\sqrt2\right) \\ &\approx& 5.2746\;. \end{eqnarray} $$

The calculation for three dimensions becomes almost trivial:

$$ \begin{eqnarray} V_3 &=& 2^33!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_2}\int_0^{\sec\phi_1}r^2\cos\phi_1\mathrm dr\mathrm d\phi_1\mathrm d\phi_2 \\ &=& 2^33!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_2}\frac13\sec^2\phi_1\mathrm d\phi_1\mathrm d\phi_2 \\ &=& 2^33!\int_0^{\pi/4}\frac13\sin\phi_2\mathrm d\phi_2 \\ &=& 8(2-\sqrt2) \\ &\approx& 4.6863\;. \end{eqnarray} $$

With all these integrals miraculously working out, one might be tempted to conjecture that there's a pattern here, with a closed form for all dimensions, and perhaps even that the sequence $4,4.69,5.27,5.50,\dotsc$ monotonically converges. However, that doesn't seem to be the case. For six dimensions, the integrals become intractable:

$$ \begin{eqnarray} V_6 &=& 2^66!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_5}\int_0^{\arctan\sin\phi_4}\int_0^{\arctan\sin\phi_3}\int_0^{\arctan\sin\phi_2}\int_0^{\sec\phi_1}r^5\cos^4\phi_1\cos^3\phi_2\cos^2\phi_3\cos\phi_4\mathrm dr\mathrm d\phi_1\mathrm d\phi_2\mathrm d\phi_3\mathrm d\phi_4\mathrm d\phi_5 \\ &=& 2^66!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_5}\int_0^{\arctan\sin\phi_4}\int_0^{\arctan\sin\phi_3}\int_0^{\arctan\sin\phi_2}\frac16\sec^2\phi_1\cos^3\phi_2\cos^2\phi_3\cos\phi_4\mathrm d\phi_1\mathrm d\phi_2\mathrm d\phi_3\mathrm d\phi_4\mathrm d\phi_5 \\ &=& 2^66!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_5}\int_0^{\arctan\sin\phi_4}\int_0^{\arctan\sin\phi_3}\frac16\sin\phi_2\cos^3\phi_2\cos^2\phi_3\cos\phi_4\mathrm d\phi_2\mathrm d\phi_3\mathrm d\phi_4\mathrm d\phi_5 \\ &=& 2^66!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_5}\int_0^{\arctan\sin\phi_4}\left[-\frac1{24}\cos^4\phi_2\right]_0^{\arctan\sin\phi_3}\cos^2\phi_3\cos\phi_4\mathrm d\phi_3\mathrm d\phi_4\mathrm d\phi_5 \\ &=& 2^66!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_5}\int_0^{\arctan\sin\phi_4}\frac1{24}\left(1-\left(1+\sin^2\phi_3\right)^{-2}\right)\cos^2\phi_3\cos\phi_4\mathrm d\phi_3\mathrm d\phi_4\mathrm d\phi_5 \\ &=& 2^66!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_5}\left[\frac1{48}\left(\phi_3+\sin\phi_3\cos\phi_3-\frac1{\sqrt2}\arctan\left(\sqrt2\tan\phi_3\right)-\frac{\sin\phi_3\cos\phi_3}{1+\sin^2\phi_3}\right)\right]_0^{\arctan\sin\phi_4}\cos\phi_4\mathrm d\phi_3\mathrm d\phi_4\mathrm d\phi_5 \\ &=& 2^66!\int_0^{\pi/4}\int_0^{\arctan\sin\phi_5}\frac1{48}\left(\arctan \sin \phi_4 + \frac{\sin \phi_4}{1 + \sin^2 \phi_4}-\frac1{\sqrt2}\arctan\left(\sqrt2\sin \phi_4\right)-\frac{\sin \phi_4}{1 + 2 \sin^2\phi_4}\right) \cos \phi_4\mathrm d\phi_4\mathrm d\phi_5 \\ &=& 2^66!\int_0^{\pi/4}\left[\frac1{96} \sin\phi_4 \left(2 \arctan\sin\phi_4-\sqrt2\arctan\left(\sqrt2 \sin\phi_4\right)\right)\right]_0^{\arctan\sin\phi_5}\mathrm d\phi_5 \\ &=& 480\int_0^{\pi/4}\sin\arctan\sin\phi_5 \left(2 \arctan\sin\arctan\sin\phi_5-\sqrt2\arctan\left(\sqrt2 \sin\arctan\sin\phi_5\right)\right)\mathrm d\phi_5 \\ &\approx& 5.3361 \;. \end{eqnarray} $$

Wolfram|Alpha doesn't find a closed form for that last integral (and I don't blame it), so it seems that you may have asked for the last of these volumes that can be given in closed form. Note that $V_2<V_3<V_4<V_5>V_6$. The results from Monte Carlo integration for higher dimensions show a monotonic decrease thereafter. This is also the behaviour of the volume of the unit hypersphere:

$$ \begin{array}{|c|c|c|c|c|c|} d&\text{sphere}&\text{cylinders}&\text{sphere}&\text{cylinders}&\text{ratio}\\ \hline 2&\pi&4&3.1416&4&1.2732\\ 3&4\pi/3&8(2-\sqrt2)&4.1888&4.6863&1.1188\\ 4&\pi^2/2&12\left(\pi-2\sqrt2\arctan\sqrt2\right)&4.9348&5.2746&1.0689\\ 5&8\pi^2/15&2^8\left(\frac\pi{12}+\frac{\mathrm{arccot}\sqrt2-\arctan\sqrt2}{\sqrt2}\right)&5.2638&5.5036&1.0456\\ 6&\pi^3/6&&5.1677&5.3361&1.0326\\ 7&16\pi^3/105&&4.7248&4.8408&1.0246\\ 8&\pi^4/24&&4.0587&4.1367&1.0192\\ \hline \end{array} $$

The ratio seems to converge to $1$ fairly rapidly, so in high dimensions almost all of the intersection of the cylinders lies within the unit hypersphere.

P.S.: Inspired by leonbloy's approach, I improved the Monte Carlo integration by integrating the admissible radius over uniformly sampled directions. The standard error was less than $10^{-5}$ in all cases, and the results would have to deviate by at least three standard errors to change the rounding of the fourth digit, so the new numbers are in all likelihood the correct numbers rounded to four digits. The results show that leonbloy's estimate converges quite rapdily.

share|improve this answer
8  
joriki, this answer is truly amazing. I am very grateful for your commitment to help (seemingly) total strangers. Thanks! –  The Chaz 2.0 Jul 14 '11 at 16:40
2  
wow this is more than I could've asked for. Thanks a ton for all your help! To answer your above question I had the result for 4 dimensions from plugging the problem into mathematica but it was unable to calculate the result for 5 dimensions, and I was hoping to be able to calculate it myself, which your solution allows beautifully. Thanks again! –  Ryan Jul 14 '11 at 17:33
5  
@The Chaz: Never underestimate the stranglehold an interesting problem can have :) –  Jacob Jul 14 '11 at 21:49
3  
So it seems there's a vote on my likely motivation and addiction is leading altruism 4:3? :-) –  joriki Jul 15 '11 at 8:44
    
Regarding your observation about the maximum at $V_5$, recall that that fact is merely a scale/dimension thing, for comparing these quantities we should better use spheres with unit diameter (instead or radius) (or divide all by 2^n), see math.stackexchange.com/questions/15656/… –  leonbloy Jul 15 '11 at 11:49

There's reflection symmetry in each of the coordinates, so the volume is $2^5$ times the volume for positive coordinates. There's also permutation symmetry among the coordinates, so the volume is $5!$ times the volume with the additional constraint $a\le b\le c\le d\le e$. Then it remains to find the integration boundaries and solve the integrals.

The lower bound for $a$ is $0$. The upper bound for $a$, given the above constraints, is attained when $a=b=c=d=e$, and is thus $\sqrt{1/4}=1/2$. The lower bound for $b$ is $a$, and the upper bound for $b$ is again $1/2$. Then it gets slightly more complicated. The lower bound for $c$ is $b$, but for the upper bound for $c$ we have to take $c=d=e$ with $b$ given, which yields $\sqrt{(1-b^2)/3}$. Likewise, the lower bound for $d$ is $c$, and the upper bound for $d$ is attained for $d=e$ with $b$ and $c$ given, which yields $\sqrt{(1-b^2-c^2)/2}$. Finally, the lower bound for $e$ is $d$ and the upper bound for $e$ is $\sqrt{1-b^2-c^2-d^2}$. Putting it all together, the desired volume is

$$V_5=2^55!\int_0^{1/2}\int_a^{1/2}\int_b^{\sqrt{(1-b^2)/3}}\int_c^{\sqrt{(1-b^2-c^2)/2}}\int_d^{\sqrt{1-b^2-c^2-d^2}}\mathrm de\mathrm dd\mathrm dc\mathrm db\mathrm da\;.$$

That's a bit of a nightmare to work out; Wolfram Alpha gives up on even small parts of it, so let's do the corresponding thing in $3$ and $4$ dimensions first. In $3$ dimensions, we have

$$ \begin{eqnarray} V_3 &=& 2^33!\int_0^{\sqrt{1/2}}\int_a^{\sqrt{1/2}}\int_b^{\sqrt{1-b^2}}\mathrm dc\mathrm db\mathrm da \\ &=& 2^33!\int_0^{\sqrt{1/2}}\int_a^{\sqrt{1/2}}\left(\sqrt{1-b^2}-b\right)\mathrm db\mathrm da \\ &=& 2^33!\int_0^{\sqrt{1/2}}\frac12\left(\arcsin\sqrt{\frac12}-\arcsin a-a\sqrt{1-a^2}+a^2\right)\mathrm da \\ &=& 2^33!\frac16\left(2-\sqrt2\right) \\ &=& 8\left(2-\sqrt2\right)\;. \end{eqnarray}$$

I've worked out part of the answer for $4$ dimensions. There are some miraculous cancellations that make me think that a) there must be a better way to do this (perhaps anon's answer, if it can be fixed) and b) this might be workable for $5$ dimensions, too. I have other things to do now, but I'll check back and if there's no correct solution yet I'll try to finish the solution for $4$ dimensions.

share|improve this answer
1  
This is exactly what I was looking for, and it agrees with the answer I have for 4 dimensions. I'll see if it can be simplified further, but thanks a ton for the help so far! –  Ryan Jul 12 '11 at 3:48
    
@Ryan: Any luck? –  Jacob Jul 12 '11 at 22:58
    
I worked out $V_4$ and got the answer that you wrote in a comment, $12\pi-24\sqrt2\arctan\sqrt2$. I don't really feel like writing it all out here, unless that would be of value to you :-). I'm not sure I understand what you've been saying in the comments -- your comment above sounds as if you worked out the integral for $V_4$ yourself? Or did you get that result using a different method? –  joriki Jul 13 '11 at 12:03

Here's how I'd tackle the problem (i.e. a starting point). For some intuition, reduce the problem to 3D. Now, you have 3 right-angled cylinders intersecting each other:

enter image description here enter image description here enter image description here

This article gives a solution to compute the volume of the intersection in 3D ; do you think it can be extended to 5D?

share|improve this answer
    
I don't see where that page gives the solution for three cylinders -- as far I can tell, all the calculations are for two cylinders. –  joriki Jul 12 '11 at 1:50
1  
Yeah, MathWorld, as a knowledge base, is pretty notorious IMO for rarely having reasonable explanations of its solutions. However, it did have a calculation for 3 cylinders (with the expectation the reader should figure out the basis for it, of course). The key insight I got from the article was "Noting the solid has a square cross-section" (for the 2-cylinder case), which enabled me to generalize to five hypercylinders in five dimensions. –  anon Jul 12 '11 at 2:30

It is clear that the valid region lies between the hyperspheres of radius $r_1=1$ and $r_2=\sqrt{5/4}$. This already gives some trivial bounds, but the upper bound is not tight. Lets try to compute the excess volume, beyond the unitary sphere.

Let fix some $1<r<r_2$. The valid region over that surface corresponds to the points with $|x_i|>\sqrt{r^2-1}$ ($\forall i$). We wish to compute $p(r)$, the proportion of the surface that lies in that region, i.e. the probability that if we throw a random point uniformily over a hypershpere surface, all its coordinates are greater than some value. This happens to be closely related to other recent question. The approximation I proposed there, using independent gaussians, can also be applied here, and we can expect to perform better (because we are interested in a more "probable" region). Applying the same reasoning, ($n$ gaussians with variance $r/n$ here, and $\epsilon = \sqrt{r^2-1}$), we get the approximation:

$$p(r) \approx \left[ 1 - erf\left(\sqrt{ n \, \frac{r^2-1}{2 r}}\right)\right]^n$$

and from this we can compute the total volume integrating:

$$ V(n) = V_1(n) + V_e(n) = \frac{\pi^{n/2}}{\Gamma{(\frac{n}{2}+1})} + n \frac{\pi^{n/2}}{\Gamma{(\frac{n}{2}+1})} \int_1^{r_2} p(r) \; r^{n-1} dr$$

where $r_2 = \sqrt{\frac{n}{n-1}}$. Pluggin the above approximation, I get these values:

 n       A       J        Ae      Je
---------------------------------------
 2    3.7664   4.0000   0.6248   0.8584
 3    4.6359   4.6863   0.4471   0.4975
 4    5.2619   5.2746   0.3271   0.3398
 5    5.5004   5.5036   0.2366   0.2398
 6    5.3353   5.3361   0.1676   0.1684
 7    4.8406   4.8408   0.1158   0.1160
 8    4.1366   4.1367   0.0779   0.0780

where column A is my approximation, J are the values from Joriki's answer (Montecarlo integration for $n>5$). The columns Ae,Je show the respective excess volumes over the unitary hypersphere, they are actually the relevant quantities to be compare to judge the goodness of the approximation. (I must say I'm surprised that gives so good results for small $n$, and the speed of convergence)

Here goes the Octave/Matlab code:

clear
global N=5
r2=sqrt(N/(N-1));

function pp=pp(r)
 global N;
 pp = (1-erf( sqrt( N* (r.^2 - 1)./(2*r) ) )).^N .* r.^(N-1);
endfunction

(pi^(N/2)/gamma(N/2+1)) * ( 1 + quad ("pp",1,r2) * N)
share|improve this answer
    
This is nice -- it converges quite rapidly! I realized from this that I could improve my Monte Carlo integration by sampling the admissible radius at uniformly distributed directions. That yields numbers to four-digit accuracy; I took the liberty to edit those into your table to enhance the comparison, which turns out to be quite favourable. You could add the difference from the hyperspherical volume to the table, since that's what you're actually approximating. –  joriki Jul 15 '11 at 8:41
    
@joriki: I actually wake up this morning thinking on adding those two columns. Done. :-) –  leonbloy Jul 15 '11 at 11:24

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.