The volume of the intersection of balls

Fix two positive numbers {R} and {r}. The volume of the intersection of balls of radii {R} and {r} is a function of the distance {d} between their centers. Is it a decreasing function?

Intersecting balls
Intersecting balls

Wolfram MathWorld gives a formula for this volume in the three-dimensional case

\displaystyle    V(d) = \frac{\pi}{12 d} (R+r-d)^2(d^2+2rd-3r^2+2Rd+6Rr-3R^2)

(Here and in the sequel it is assumed that {d\le R+r}.) From this formula it is not at all obvious that {V(d)} is decreasing. And this is just for three dimensions.

Let’s begin with the one-dimensional case, then. Consider the intervals {[-R,R]} and {[d-r,d+r]} where {d\le R+r}. A point {x} belongs to their intersection if and only if

\displaystyle  \max(-R,d-r)\le x \le \min(R,d+R)

Hence, the length of the intersection is {L(d)=\min(R,d+r)-\max(-R,d-r)}. Even this simple formula does not quite make it evident that the function is decreasing for {d>0}. If {d+r>R} this is clear enough, but the case {d+r -d-r>-r}.

Fortunately, Fubini’s theorem reduces the general case to the one-dimensional one. Take any line {L} parallel to the line connecting the centers. The intersection of each ball with {L} is a line segment whose length is independent of {d}. The distance between the midpoints of these segments is {d}; thus, the length of the intersection is a decreasing function of {d}.

Gromov’s note Monotonicity of the volume of intersection of balls (1987) deals with the more general case of {k\le n+1} balls in {\mathbb R^n}: if two sets of balls {B(x_i,r_i)} an {B(x_i',r_i)} satisfy {\|x_i'-x_j'\|\le \|x_i-x_j\|} for all {i,j}, then the volume of {\bigcap B(x_i,r_i)} does not exceed the volume of {\bigcap B(x_i',r_i)}.

The paper ends with

Question: Who is the author of [this result]? My guess is this was known to Archimedes. Undoubtedly the theorem can be located […] somewhere in the 17th century.

Meanwhile, the corresponding problem for the volume of the union remains open.

Rectangular boxes: handle with care

A rectangular box (aka parallelepiped) looks like a sturdy object:

Rainbow sheep inside
Rainbow sheep inside

But this particular box, with dimensions 7.147 by 6.021 by 4.095, took me the better part of an hour to figure out.

It was a part of a numerical methods assignment: find the dimensions of a box with given volume {V}, surface area {S}, and diameter {D} (i.e., space diagonal). Algebraic approach leads to pretty ugly expressions, which is the motivation for a numerical method. Specifically, the task was to apply the Newton-Raphson method to the map

\displaystyle    F(x,y,z) = \begin{pmatrix} xyz-V  \\ 2(xy+yz+xz)-S  \\ x^2+y^2+z^2-D^2 \end{pmatrix}

Of course, I understood that not every triple {(V,S,D)} is attainable. Also realized that the Jacobian of {F} is degenerate when two of the coordinates coincide, which is a problem for the method. So I thought: let’s generate some random {x,y,z} values that are not too close to one another, and give students the resulting parameters {V,S,D}.

With {x=7.147}, {y=6.021}, and {z=4.095} the parameters are {V=176.216}, {S=193.91}, and {D=10.203}. Sure, a little rounding can’t hurt when numbers are of this size and we are quite far from the critical points of {F}. So I put {V=176}, {S=194} and {D=10} in one of the versions of the assignment.

But the Newton-Raphson method would not converge… because no such box exists! The rounding did hurt after all.

This motivated me to describe all attainable triples {(V,S,D)} explicitly, which ended up being less of a chore than I expected. It helps to realize that {(x+y+z)^2 = D^2+S}, which reduces the search to the intersection of the sphere {x^2+y^2+z^2=D^2} with the plane {x+y+z=\sqrt{D^2+S}}. This is a circle (called {C} below), and the allowed range for {V} is between the minimum and maximum of {xyz} on {C}.

This goes into Calculus 3 territory. Using Lagrange multipliers with two constraints looks like a tedious job. Instead, I decided to parametrize {C}. Its center is {(c,c,c)} where {c=\dfrac13\sqrt{D^2+S}}. The radius is {\displaystyle r = \sqrt{ D^2 - \frac13(D^2+S)}=\frac13 \sqrt{6D^2-3S}}. We also need an orthonormal basis of the subspace {x+y+z=0}: the vectors

\displaystyle  \frac{1}{\sqrt{6}} \langle 2, -1, -1\rangle \quad \text{and}\quad \frac{1}{\sqrt{2}} \langle 0, 1, -1\rangle

do the job.

So, the circle {C} is parametrized by

\displaystyle    x  = c+\frac{2r}{\sqrt{6}} \cos t \\   y  = c-\frac{r}{\sqrt{6}} \cos t +\frac{r}{\sqrt{2}} \sin t \\   z  = c-\frac{r}{\sqrt{6}} \cos t -\frac{r}{\sqrt{2}} \sin t

This is not as bad as it looks: the product {xyz} simplifies to

\displaystyle xyz = c^3 - \frac{cr^2}{2} + \frac{r^3\sqrt{6}}{18} \cos 3t

which tells us right away that the volume {V} lies within

\displaystyle  c^3 - \frac{cr^2}{2} \pm \frac{r^3\sqrt{6}}{18}

In terms of the original data {S,D} the bounds for {V} take the form

\displaystyle    \frac{5S-4D^2}{54}\sqrt{S+D^2} \pm \frac{\sqrt{2}}{54} (2D^2-S)^{3/2}

(And of course, {V} cannot be negative even if the lower bound is.) It is easy to see that {2D^2-S\ge 0} with equality only for a cube; however {2D^2-S} can be relatively small even when the box does not look very cube-ish. For the box pictured above, the tolerance {\frac{\sqrt{2}}{54} (2D^2-S)^{3/2}} is approximately {1.4}; after rounding {S\approx 194 } and {D\approx 10} this drops to {0.38}, and the desired volume of {176} is way out of the allowable range {181\pm 0.38}.

Yes, the set of attainable triples {(V,S,D)} is quite thin. Parallelepipeds are fragile objects: handle them with care.

Attainable (V,S,D)
Attainable (V,S,D)

Interpolating between a cone and a cylinder

This post is inspired by James Tanton’s video which is summarized in bulleted items below. For convenience normalize all solids to height {1}.

  • Parallel cross-sections of a cylinder have constant area. Therefore its volume is {\int_0^1 A z^0\,dz =Ah}, where {A} is the area of the base.
  • Parallel cross-sections of a cone are scaled in both directions by the {z}-coordinate. This multiplies the sectional area by {z^2} and therefore the volume is {\int_0^1 A z^2\,dz =\frac{1}{3}Ah}.
  • There is something in between: we can scale cross-sections in one direction only. Then the sectional area is multiplied by {z} and the volume is {\int_0^1 A z\,dz =\frac{1}{2}Ah}.

Taking the base to be a circle, we get this shape:

Pinched in one direction
Pinched in one direction

It looks… odd. Not even convex:

Convexity is lost
Convexity is lost

But cones and cylinders are convex whenever the base is a convex region. Can we interpolate between them within the class of convex sets?

The answer is: yes, if we use the Minkowski sum. Given two convex bodies {A_0} and {A_1} in {{\mathbb R}^3}, for {0< t<1} define

\displaystyle  A_t =(1-t)A_0+tA_1 = \{(1-t)a_0+ta_1 : a_0\in A_0, a_1\in A_1\}

Each {A_t} is convex. If the sets {A_0} and {A_1} are cone and cylinder of equal height and with the same convex base {B}, then all {A_t} have the same base and the same height.

Finding the volume of a convex body in Calculus II/III can be a tiresome exercise with trigonometric substitutions and whatnot. It may come as a surprise that the volume of {A_t} is always a cubic polynomial in {t}, even if the convex sets {A_0, A_1} are defined by some transcendental functions. I still do not find this fact intuitive.

Let’s check it on the example of {A_0} and {A_1} being a cone and a cylinder of height {1} and radius {r}. Obviously, every {A_t} is a solid of revolution. Its profile is the Minkowski sum of appropriately scaled triangle and rectangle. This is how I imagine it:

  • Mark a point on the rectangle, for example the midpoint of the bottom edge.
  • Move the rectangle around so that the marked point stays within the triangle.
  • The region swept is the Minkowski sum.
Minkowski sum
Minkowski sum

The volume can now be computed directly. I used the venerable method of cylindrical shells to find the volume of {A_1\setminus A_t}:

\displaystyle 2\pi \int_{tr}^t x(x/r-t)\,dx = \frac{\pi r^2}{3}(2-3t+t^3)

hence

\displaystyle  \mathrm{Vol}\, (A_t) = \frac{\pi r^2}{3}(1+3t-t^3)

It so happens that {\mathrm{Vol}\,(A_t)} is a concave function in this example, although in general only its cubic root is guaranteed to be concave, by the Brunn-Minkowski inequality.

When {t\approx 0.168}, the volume of {A_t} is equal to {\pi r^2/2}, same as the volume of James Tanton’s solid. Since {t} is pretty small, the shape looks much like a cone.

1/2 of area*height
Half of Area*Height

When {t\approx 0.347}, the volume of {A_t} is equal to {2\pi r^2/3}, which is exactly halfway between the volumes of cone and cylinder. The solid exhibits harmonious balance of both shapes.

2/3 of area*height
2/3 of area*height

Archimedean volume ratio

And although he made many excellent discoveries, he is said to have asked his kinsmen and friends to place over the grave where he should be buried a cylinder enclosing a sphere, with an inscription giving the proportion by which the containing solid exceeds the contained.

Sphere and cylinder

(Quote from Plutarch; see references on the Archimedes site by Chris Rorres. Image from Wikipedia)

The proportion is 3:2, as Archimedes discovered. More generally, let A_n be the ratio of the volumes of n-dimensional unit ball B^n and of the circumscribed cylinder B^{n-1}\times [-1,1]. This sequence begins with A_1=1, A_2=\pi/4, A_3=2/3, A_4=3\pi/16, A_5=8/15, A_6=5\pi/12\approx 0.49\dots. Note that beginning with 6 dimensions, the ball occupies less than half of the cylinder. It is not hard to see that the sequence monotonically decreases to zero. Indeed, the ratio of (n-1)-dimensional cross-sections by the hyperplane x_{n}=t, for -1\le t\le 1, is (1-t^2)^{(n-1)/2}. Hence A_n = \frac{1}{2} I_{(n-1)/2} where I_p:=\int_{-1}^1 (1-t^2)^p\,dt. The integrand monotonically converges to 0 a.e. as p\to\infty, and therefore I_p does the same.

The Archimedean ratio A_n is rational when n is odd, and is a rational multiple of \pi when n is even. Indeed, integrating I_p by parts, we get
\displaystyle I_p = \int_{-1}^1 (1-t^2)^p\,dt = 2p \int_{-1}^1 t^2(1-t^2)^{p-1}\,dt = 2p(I_{p-1}-I_{p})
hence I_p = \frac{2p}{2p+1}I_{p-1}. In terms of A_n = \frac{1}{2} I_{(n-1)/2}, we have A_{n}= \frac{n-1}{n}A_{n-2}. Since A_1=1 and A_2=\pi/4 are known (the former being trivial and the latter being one of definitions of \pi), the claim follows.

Combining the monotonicity with the recurrence relation, we find that \displaystyle \frac{n-1}{n} =\frac{A_{n}}{A_{n-2}} \le \frac{A_{n}}{A_{n-1}}\le 1. Hence \displaystyle \frac{A_{n}}{A_{n-1}} \to 1, which yields the Wallis product formula for \pi. Indeed, the recurrence shows that for n even, \displaystyle  \frac{A_{n}}{A_{n-1}} is a particular rational multiple of \displaystyle \frac{A_{2}}{A_{1}} = \frac{\pi}{4}.

The above is essentially the inductive proof of Wallis’s formula I remember from my calculus (/real analysis) class. Unfortunately, between integration by parts and the squeeze lemma we lose geometry. In geometric terms, Wallis’s formula says that the volumes of B^{n+1}\times B^{n-1} are B^n\times B^n are asymptotically equivalent: their ratio tends to 1. Is there a way to see that these solids have a large overlap? Or, to begin with, that B^{n+1}\times B^{n-1} has the smaller volume? I don’t see this even with B^3\times B^1 vs B^2\times B^2. By the way, the latter is the bidisc from complex analysis.

Aside: Wallis’s formula for statistics students by Byron Schmuland presents a nice 2-page proof (which uses the relation between \pi and the Gaussian).

Added: Another way to generalize the Archimedean volume ratio to higher dimensions is to divide the volume of B^{2n+1} by the volume of B^{n}\times B^{n+1}. The quotient is always rational, namely \displaystyle \frac{(n+1)!}{(2n+1)!!}. The sequence begins with \displaystyle 1, \frac23, \frac25, \frac{8}{35}, \frac{8}{63}, \frac{16}{231}, \frac{16}{429} and obviously tends to zero. It does not appear to be related to \pi.