12
$\begingroup$

There is a number of similar questions already (e.g. this one), but as far as I can see, none quite cuts it for me.

In $n$-dimensional euclidean space, a hypercube $H$ with side lengths $2A$ is centered around the origin. So is a hypersphere $S$ with radius $x$. What is the fraction of volume of the hypercube $H$ that is also inside the hypersphere $S$, that is, what is the volume of $H\cap S$?

As calculating the fraction with respect to the hypercube is trivial by just dividing by its volume in the end, it boils down to calculating the volume of the intersection. My first idea was to separate three different cases:

  1. If $x<A$ the hypersphere is fully contained in the hypercube. Then, the volume is simply the volume of the hypersphere, for which there are analytical formulae.
  2. If $x^2> n \cdot A^2$, the hypercube is fully contained in the hypersphere. In this case, the volume is simply that of the hypercube, that is, $(2A)^n$.
  3. For intermediate values of $x$, the intersection is given as the volume of the hypersphere minus $2n$ hyperspherical caps, for which there is also a closed form solution (e.g. here)

After my calculation consistently gave wrong results, I was forced to admit that the case (3) is more difficult than I thought, because as soon as the opening angle of the hypercaps is larger than $\pi/4$, they start to intersect along the edges of the hypercube, whereas the corners are still outside the intersection volume. For $n=3$, this can be seen in this graphic, which was generated by wolframalpha.

cirle-cube-intersection in 3D

Thus, the solution proposed in (3) double-counts these volumes.

I can't seem to come up with general solution to calculate this, because counting (and calculating) the intersection areas is very tedious.

Is there any closed-form, analytic solution available for this problem?

$\endgroup$

3 Answers 3

Reset to default
8
+50
$\begingroup$

The complexity here comes from the fact that in $n$ dimensions there are $n-1$ types of extended boundaries of the hypercube (in which $1,2,\ldots,n-1$ coordinates are maxed-out at $\pm A$). So, while in $3$ dimensions there are only edges and faces, the nomenclature of "caps" and "corners" does not capture the behavior in higher dimensions. The hypersphere starts intersecting the boundaries of type $j$ when its radius reaches $A\sqrt{j}$, and only fully contains them when its radius exceeds $A\sqrt{n}$, so we expect the final formula to be non-smooth at $n$ different radii.

However, we can find a reasonably simple recursive form. Let $V_n(R)$ be the volume of the intersection in $n$ dimensions when the hypersphere has radius $R$ and the hypercube has side length $2$. Then $$ V_n(R)=\int_{x_1=-1}^{+1}\int_{x_2=-1}^{+1}\cdots\int_{x_n=-1}^{+1}I\left[\sum_{i=1}^{n}x_i^2 < R^2\right]dx_1 dx_2 \cdots dx_n, $$ where $I(\Phi)$ is $1$ when $\Phi$ is true and $0$ otherwise. The integrand is nonzero only when $|x_1|<R$, in which case we have $$ I\left[\sum_{i=1}^{n}x_i^2 < R^2\right]=I\left[\sum_{i=2}^{n}x_i^2 < R^2-x_1^2\right]; $$ so $$ V_n(R)=\int_{x=-\min(1,R)}^{+\min(1,R)}V_{n-1}\left(\sqrt{R^2-x^2}\right)dx. $$ The base of the recursion is $V_0(R)=1$; or, if the $0$-dimensional volume seems too contrived, $V_1(R)=2\min(1,R)$.

$\endgroup$
2
  • $\begingroup$ Reviving an old thread, so sorry if you don't know the answer, I was wondering where I can find a reference and more detail/proof regarding "The hypersphere starts intersecting the boundaries of type jj when its radius reaches Aj√Aj, and only fully contains them when its radius exceeds An‾√An". Thanks $\endgroup$
    – Sam Palmer
    Commented Jun 7, 2018 at 15:36
  • 3
    $\begingroup$ @SamPalmer: I'm defining the "boundaries of type $j$" as the sets of points $(x_1,x_2,\ldots,x_n)$ where $j$ of the $x_i$ are equal to $\pm A$. Since the other $x_i$ can have absolute value anywhere from $0$ to $A$, $\sum_i x_i^2$ can have any value from $jA^2$ to $nA^2$, from which the statement follows. $\endgroup$
    – mjqxxxx
    Commented Jun 11, 2018 at 14:58
1
$\begingroup$

Not sure if this will be heplful (it seems to get very messy), but one can set up the integrals for the volumes of a 'corner' (in the case that $H\backslash S$ is disconnected)

$$\int_{\sqrt{R^2-(n-1)A^2}}^{A}\int_{\sqrt{R^2-(n-2)A^2-x_1^2}}^A...\int_{\sqrt{R^2-A^2-x_1^2-...-x_{n-2}^2}}^A\int_{\sqrt{R^2-x_1^2-...-x_{n-1}^2}}^A~dx_ndx_{n-1}dx_{n-2}...dx_1.$$

Let the volume of this be $C(n,R,A)$ as there are $2^n$ such 'corners' all with equal volume, so your intersection's volume is

$$2^n(A^n-C(n,R,A)).$$

Perhaps the formula $$C(n,R,A)=\int_{\sqrt{R^2-(n-1)A^2}}^A C(n-1, \sqrt{R^2-x_1^2}, A)~dx_1$$

could be useful to inductively compute the integrals for these cases...

$\endgroup$
8
  • 1
    $\begingroup$ That looks very interesting... I already thought of calculating the corner volumes instead, but didn't manage to write down their definitions properly. However, it's not clear to me whether these integrals can necessarily be solved. Do you have any suggestion of how to solve these efficiently? Also, this would then be a case (4), as the approach with the caps would still be required p to the point where disjoint caps exist, right? $\endgroup$
    – carsten
    Commented Nov 6, 2016 at 20:07
  • $\begingroup$ Yeah, I'm not sure of a nice way to compute them either...I'll give it another try and let you know if I get anywhere. Right, I was thinking that either the caps are disjoint or the corners are disjoint, but that was just based off looking at your picture. $\endgroup$
    – Khanickus
    Commented Nov 6, 2016 at 21:13
  • $\begingroup$ After thinking this through a bit, I think that this approach would actually work in the sense that the caps overlap if and only if the corners are disjoint - only the radius at which this happens will depend on the dimensionality... $\endgroup$
    – carsten
    Commented Nov 7, 2016 at 0:10
  • 1
    $\begingroup$ It sounds like the claim here is that either $B^n\setminus I^n$ is disconnected (in which case it consists of $2n$ identical cap pieces) or $I^n\setminus B^n$ is disconnected (in which case it consists of $2^n$ identical corner pieces). This is certainly true in the $n=3$ case because as the ball grows, the geometry goes from 'no surface intersection of the ball with the 1-faces (i.e. edges) or 2-faces' to 'intersects the 2-faces but not the 1-faces' to 'intersects the 1-faces' to 'no surface intersection' again, but I'm having a hard time believing that holds up in higher dimensions. $\endgroup$
    – Steven Stadnicki
    Commented Nov 10, 2016 at 23:45
  • 1
    $\begingroup$ In particular, what if we take $I^4 = [-1,1]^4$ and look at a ball $B$ of radius $\sqrt{5/2}$? Such a ball intersects the surface 3-faces (which are distance 1 away from the origin) and the surface 2-faces (which are distance $\sqrt{2}$ away from the origin), but not the surface 1-faces (which are distance $\sqrt{3}$ away from the origin). $\endgroup$
    – Steven Stadnicki
    Commented Nov 10, 2016 at 23:48
1
$\begingroup$

There are some explicit formula without nested integral from Constales & Tibnek (1997). The paper is behind paywall, though the formula and generalization can also be found at

https://arxiv.org/pdf/1804.07861.pdf

and Section 5 of

https://eprint.iacr.org/2017/155.pdf

$\endgroup$
1
  • 1
    $\begingroup$ There was a small error in the original solution of Constales [1], which was reported in [2]. The newest revision of [2] is corrected. Funnily enough, in generalising the formula, the authors of [3] fixed this error. For what it's worth, I have made a small implementation of the method of Constales, that truncates the infinite sum and calculates its Fresnel integrals to a finite precision here github.com/verdiverdiverdi/ball-box [1]: Problems and solutions. SIAM Review, 39(4):761–789, 1997 [2]: arxiv.org/pdf/1804.07861.pdf [3]: eprint.iacr.org/2017/155.pdf $\endgroup$
    – E. Postlethwaite
    Commented Oct 24, 2022 at 17:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .