The curse of dimensionality

Finding the diameter of a $2$ -dimensional centre disk

Exercise (Finding the diameter of a

2

-dimensional centre disk)

Given a unit square, place $4$ disks in the square, one in each corner such that all the disks are as large as possible, of equal size, and without intersecting. Then place a 5th disk in the centre (equidistant from the four disks) such that it is as large as possible, without intersecting. Find the diameter of the centre disk.

Answer

\frac{\sqrt{2}-1}{2} = 0.207\dots.

Proof (Geometric Approach)

Creating the structure we have:

Figure 1.

Drawing a line through the diagonal of the square, we find that the length of the line is $\sqrt2$ .

Figure 2.

Intuition

Notice that drawing a line diagonally through the square slices the centre disk in half. The length of the whole line is $\sqrt2$ , and intuitively you can solve this by cutting off the pieces of the diagonal line which are outside of the centre disk, which leaves you with the diameter of the centre disk. Another way of thinking about this is in terms of vectors; since the diagonal line is one long vector, we can scale it down by multiplying it by some constant $C$ , where $C \in \R$ , so that its length matches the centre disks diameter. i.e. $C\sqrt2$ .

Figure 3.

If we look at Figure 1 $\space$ more globally, with say, a $3 \times 3$ matrix, we get:

Figure 4.

Notice that within the $3\times3$ matrix, there exist gaps that we can fill.

Figure 5.

Important

Notice two facts: The gaps we filled are being sliced through the centre, vertically and horizontally, and are of equal size to the centre disk. These two facts will help us reach the solution.

Looking at Figure 2 $\space$ we can see that part of the diagonal line crosses through empty space. We can calculate the length of that empty space by looking at Figure 6. $\space$ $1/4$ th of the disk we filled takes up the space of the corners. The two empty spaces sum to the diameter of the centre disk across the diagonal line. Because our line contains two diameters of the centre disk, we can divide $\sqrt2$ by $2$ to get closer to the diameter of the centre disk.

\frac{\sqrt2}{2} = \text{Length of diagonal line (minus the empty space)}.

Looking at Figure 2, (the half intersected disks), notice that two larger disks (top right and bottom left disks) are also intersected through the centre. The length of each disk is $1/2,$ and so subtracting that from our current diagonal line (minus the empty space) would give us the diameter of the centre disk.

\begin{aligned} \frac{\sqrt{2} - \left(\frac12 + \frac12\right)}{2} = \frac{\sqrt{2} - 1}{2} = 0.207\dots \tag*{$\blacksquare$} \end{aligned}

Now that we’ve solved the $2$ -dimensional case, how exactly would we approach the $3$ -dimensional case, $4$ -dimensional case, or even the general case? (i.e., the $n$ -dimensional case). By studying the invariants.

$3$ -dimensional case

Example (Finding the diameter of a

3

-dimensional centre disk)

We’ll solve this by seeing what invariants remain when moving from the 2-dimensional case to the 3-dimensional case.

Recall

The diameter of the centre disk in $2D$ is

\frac{\sqrt{2}-1}{2}.

$\sqrt2$ $\space$ calculates the length of the diagonal of the square. $\newline$ $\sqrt2-1$ $\space$ subtracts the two larger disks length (top right and bottom left) from the squares diagonal. $\newline$ $\sqrt2/2$ $\space$ removes the duplicate diameter from the two empty spaces.

Being able to replicate what these evaluate to in $3$ D is our goal. Calculating the diagonal of a cube follows from the 3-dimensional case of Pythagorean theorem

d=\sqrt{x^2+y^2+z^2},

where $x,y,z \in \R$ such that $d\in\R_{\geq 0}.$

Note

Pythagoreans theorem also generalises to $n$ -dimensions.

Evaluating Pythagoreans theorem in $3D$ (for a unit-cube) returns $d=\sqrt{1^2+1^2+1^2}=\sqrt3,$ and so the length of the diagonal of a unit-cube is $\sqrt3.$ Suprisingly subtracting the two larger balls in $3D$ is the same in $3D$ as it is in $2D$ , we are still using unit squares/cubes and so the ratios for this and the duplicate diameter remain the same. Thus the diameter for $n=3$ is:

\frac{\sqrt 3-1}{2}. \tag*{$\blacksquare$}

Summary of $n=2$ and $n=3$

Before we tackle the $n$ -dimensional case, let’s compare some properties from case $n=2$ and $n=3.$

Summary

The formula for $n=2$ $\space$ and $n=3$ $\space$ are very similar, all that’s changed is the number under the square root.

\frac{\sqrt 2-1}{2} = \text{centre disk diameter for $n=2$.}

\frac{\sqrt 3-1}{2} = \text{centre disk diameter for $n=3$.}

\text{Of course,}\space\space \frac{\sqrt 3-1}{2} > \frac{\sqrt 2-1}{2}.

Dimension	no. of balls	no. of corners in $n$ -cube
$2$	$5$	$4$
$3$	$9$	$8$

We know that the values we subtract from the length of the diagonal in the formula won’t change for any dimension, so our answer will look something like this:

\frac{\text{something}-1}{2},

where $\text{something}$ is the length of the diagonal of an $m$ -cube. And so all we have to do is prove Pythagoreans theorem generalises to $n$ -dimensions.

Pythagoreans theorem in $n$ -dimensions

Lemma (Pythagoreans theorem in

m

-dimensions)

x_1^2+x_2^2+x_3^2+\dots,+x^m=y^2,

where $x=(x_1,x_2,\dots,x_m)\in\R$ and $y=\sqrt{x_1^2+x_2^2+\dots+x_m}.$

Exercise (Prove Pythagoreans theorem generalises to

m

-dimensions)

\begin{aligned} \text{Exercise for the reader.} \tag*{$\blacksquare$} \end{aligned}

Now that we’ve proved Pythagoreans theorem generalises to $n$ -dimensions, we’ve solved the problem.

Diameter of the central $m$ -ball among corner $m$ -balls in $\mathbb{R}^n$

Theorem (Diameter of the central

m

-ball among corner

m

-balls in

\mathbb{R}^n

)

Given an $m$ -dimensional unit cube, for any $m\in \Z^+$ , place one $m$ -ball in each corner of the $m$ -cube ( $2^m$ corners) such that all the $m$ -balls are as large as possible, of equal size, and without intersecting. Then in the centre of the $m$ -cube place one more ball such that it is as large as possible, and tangent to all other corner balls. Then the centre ball’s diameter is:

\frac{\sqrt{m}-1}2.

Observations

Now that we have a generalised formula let’s look at some properties across the dimensions in more detail.

Dimension ( $m$ )	$m$ -balls $(m^2+1)$	Corners $(m^2)$	Center $m$ -ball diameter $\left(\tfrac{\sqrt{m}-1}{2}\right)$
$1$	$2$	$1$	$0$
$2$	$5$	$4$	$0.207\ldots$
$3$	$10$	$9$	$0.366\ldots$
$4$	$17$	$16$	$1/2$
$5$	$26$	$25$	$0.618\ldots$
$6$	$37$	$36$	$0.724\ldots$
$7$	$50$	$49$	$0.822\ldots$
$8$	$65$	$64$	$0.914\ldots$
$9$	$82$	$81$	$1$
$10$	$101$	$100$	$1.081\ldots$
⋮	⋮	⋮	⋮

There are many things to notice here, but I’ll focus on one part. $\left(\tfrac{\sqrt{m}-1}{2}\right)$ clearly grows without bound. Therefore,

\left(\tfrac{\sqrt{1}-1}{2}\right)\leq\left(\tfrac{\sqrt{2}-1}{2}\right)\leq\dots\leq\left(\tfrac{\sqrt{m}-1}{2}\right).

Looking at some cases of $m$ , we find that at $m=4$ , the central balls diameter is half the side length of the $m$ -cube, i.e., $1/2.$ At $m=9$ the diameter of the center ball is equal to the side length of the $m$ -cube, i.e. $1$ , and at $m=10$ the diameter of the center ball is greater than the side length of the $m$ -cube. But wait. The side length of any unit $m$ -cube is 1, and any $m\geq10$ results in the diameter of the center ball being greater than $1$ ; meaning the ball sticks outside of the box it was meant to be enclosed in! So what exactly is going on here?

The curse of dimensionality

Finding the diameter of a 222-dimensional centre disk

333-dimensional case

Summary of n=2n=2n=2 and n=3n=3n=3

Pythagoreans theorem in nnn-dimensions