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.
Volume of Region in 5D Space
-
0@Nate: Funny you should say that just now -- I was just adding something about that to my answer :-) – 2011-07-14
4 Answers
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
$ \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.
-
1@MJD: More generally, Monte Carlo integration chooses a large number of random points (distributed according to the integration measure) and calculates the average of the integrand at those points. The estimate for the integral is then the total volume being sampled times the calculated average. In the present case of computing the volume of a region, the integrand is the characteristic function of the region, so this simplifies to what you wrote, calculating the fraction of points inside the region. See http://en.wikipedia.org/wiki/Monte_Carlo_integration. – 2015-04-28
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.
-
0I 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? – 2011-07-13
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:
This article gives a solution to compute the volume of the intersection in 3D ; do you think it can be extended to 5D?
-
0Looks like they updated it with $V_3,V_4,V_6$. – 2017-03-08
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
$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)
-
0@joriki: I actually wake up this morning thinking on adding those two columns. Done. :-) – 2011-07-15