# Fully cover a hyper-rectangle by two congruent disks ($n$-balls) and find the radius of them

I want to find a general way to calculate the smallest possible radius ($R$) of two congruent $n$-disks ($n$-balls) with the centers ($C_1$) and ($C_2$) lying on the diagonal of the hyper-rectangle and fully covering him. The positions of both centers are fixed and divides the main diagonal into three equal parts. Examples of such covering for $n = 2$ and $n = 3$ cases (for simplicity I'm using there $n$-cube, but it could be any hyper-rectangle) are shown in the pictures below.

At the moment, it looks, that it would be possible to find all the distances between all rectangle vertices $V(Rect) = \{ v_i: i=1,\dots,2^n \}$ and these two center points $C_1$ and $C_2$ and then to take: $$R = \max_{v_i \in V(Rect)} \left\{ \min \left\{ \left\| v_i - C_1 \right\|, \left\| v_i - C_2 \right\| \right\} \right\},$$ However, as the number of vertices $2^n$ increase rapidly when $n$ goes up, I would like to derive a simpler way to find $R$. For example, considering only hyper-rectangle side lengths in each dimension.

covering-2D

covering-3D

• I think the $R$ shown for the second example is too small if you want to cover all of the hyper-rectangle, not just its vertices. But I believe the answer by N74 will cover everything. – David K Feb 29 '16 at 14:01
• @DavidK I made small corrections to: covering-3D. Both diagonal vertices lie inside these spheres (3-balls) while the rest 6 vertices lie on the boundary of one of these spheres. It seems, that all the points are covered. – Remis Feb 29 '16 at 14:30
• It looks the same, but actually I was wrong about this shape. The cube is an unusual case because you don't have to completely cover the entire "nearest" face with one sphere; each sphere covers the portion of each face that the other sphere fails to cover. When one dimension of the hyper-rectangle is much larger than the others, however, you are better off to use spheres that are not large enough to reach all faces. – David K Feb 29 '16 at 15:16

In the following only the case of a cube is considered.

Let $C:=[{-1},1]^n$ be the cube and $c_\pm:=\pm{1\over3}(1,1,\ldots,1)$ the two prospective centers. The plane $x_1+x_2+\ldots x_n=0$ divides $C$ into two halves $$C_+:=\bigl\{x\in C\bigm| x_1+x_2+\ldots+x_n\geq0\bigr\}$$ and $C_-:=-C_+\>$. The points in $C_+$ are lying nearer to $c_+$, hence they have to be covered by the sphere centered at $c_+$. It follows that we have to find $$\max\left\{\sum_{k=1}^n\left(x_k-{1\over3}\right)^2\biggm| x\in C_+\right\}\ .$$ Consider a point $x\in C_+$, and assume that $$-1<x_1\leq x_2<1\ .$$ Put $\delta:=\min\{x_1-(-1), 1-x_2\}$, and replace $x_1$, $x_2$ by $$x_1':=x_1-\delta,\qquad x_2':=x_2+\delta\ .$$ Then $x_1'=-1$ or $x_2'=1$, and $x_1'+x_2'=x_1+x_2$. It follows that $x':=(x_1',x_2',x_3,\ldots, x_n)\in C_+$. Since $$\left(x_1'-{1\over3}\right)^2+\left(x_2'-{1\over3}\right)^2=\left(x_1-{1\over3}\right)^2+\left(x_2-{1\over3}\right)^2 +2\delta(x_2-x_1)+2\delta^2$$ it follows that the objective function $\phi$ has strictly increased under the replacement $x\rightsquigarrow x'$.

This allows to draw the following conclusion: The optimal feasible points have at most $1$ coordinate $\ne\pm1$, hence can be written in the form $$x=\bigl((-1)^r,(+1)^{n-1-r},t\bigr)$$ with $0\leq r\leq n-1$ and $-1\leq t\leq1$. Since each entry $-1$ adds ${16\over9}$ to $\phi$, whereas a $+1$ adds only ${4\over9}$ we want $r$ as large as possible. If $2r>n$ then $$\sum_{k=1}^n x_k=-r+(n-1-r) +t<t-1<0\ ,$$ which is forbidden. It seems that $r:=\lfloor n/2\rfloor$ and $t=1$ is optimal, whether $n$ is even or odd.

Let's put one vertex of the hyper-rectangle in $O$, the opposite side will be $V_{far}=(s_1, s_2,..., s_n)$, where $s_i$ is the length of the side in the $i_{th}$ dimension.

Let's call $q$ the index where $s_q=\max\left\{s_i\right\}$. $$R = \sqrt{{1 \over 9}s_q^2+{4 \over 9}\sum_{i=1, i\ne q}^ns_i^2}$$

EDIT. How I derived this expression.

First of all let's assume $q=n$, this will obviously have no implication on the final result.

Cut the hypercube on the plane perpendicular to the diagonal. You will have that the points farther from $O$ are the ones that lie on the other side of the plane and, for all of them, the $n_{th}$ coordinate is not $0$. These points will be nearer to $C_2$.

Now we must find an hypersphere containing all the points with the $n_{th}$ coordinate $=0$. This is easy, as we have the center $C_1\equiv V_{far}/3$ and the farther point (on our side of the cut) is $P\equiv (s_1, s_2,..., s_{n-1},0)$.

So with pythagorean theorem the result is easily obtained.

Take in consideration that this is the minimum radius given the position of $C_1$. If you are allowed to move this point you can find smaller radii.

• I think instead of the term $s_q^2$ in the sum under the radical, you want $\frac19 s_q^2$. – David K Feb 29 '16 at 13:54
• Nicely spotted @DavidK! – N74 Feb 29 '16 at 13:56
• @N74 Can you please explain how you derived this formula. I want to get a better geometrical understanding why in this way obtained radius, is the smallest possible. – Remis Feb 29 '16 at 14:56
• @Remis. Just edited the answer. – N74 Feb 29 '16 at 16:10
• @N74 It gives not minimum. Let $Rect = [0,0.5]\times[0,1]\times[0,1]$ and $C_1 = (\frac{1}{6},\frac{1}{3},\frac{1}{3})$, $C_2 = (\frac{1}{3},\frac{2}{3},\frac{2}{3})$. Then, by your formula: $R = \sqrt{\frac{1}{9}\cdot 1^2 + \frac{4}{9} \cdot ( 1^2 + (\frac{1}{2})^2 )} = \sqrt{\frac{2}{3}}$ is the distance between our side center $C_1$ and $P = (\frac{1}{2},1,0)$. While point $P$ is actually closer to $C_2: \sqrt{(\frac{1}{6})^2 + (\frac{1}{3})^2 + (\frac{2}{3})^2} = \sqrt{\frac{7}{12}} < \sqrt{\frac{2}{3}}$. I believe ...the $n_{th}$ coordinate is not 0.'' is wrong. – Remis Mar 1 '16 at 20:53

I'll make it to the point with the $[0,1]^n$ cube. Your can adapt for an hyper-rectangle. Your centers lies on the diagonal. Thus $C_1 = (c_1,c_1, ..., c_1)$ and $C_2 = (c_2,c_2, ..., c_2)$.

For $C_i$, the distance with a vertex $v$ it is $$\sqrt{ (c_i-v_1)^2 + (c_i-v_2)^2 + ... + (c_i-v_n)^2 }$$

By construction, the $v_j$'s are either $0$ and $1$. Thus if $v$ has $k$ ones and $n-k$ zeroes, the formula is $$\sqrt{ k \cdot (1-c_i)^2 + (n-k) \cdot c_i^2 }$$

Thus in your formula, each minimum is actually : $$\min\left( \sqrt{ k \cdot (1-c_1)^2 + (n-k) \cdot c_1^2 }, \sqrt{ k \cdot (1-c_2)^2 + (n-k) \cdot c_2^2 } \right)$$

Since $c_1 = \frac{1}{3}$ and $c_2 = \frac{2}{3}$, this is: $$\min\left( \sqrt{ k \cdot \left(\frac{2}{3}\right)^2 + (n-k) \cdot \left(\frac{1}{3}\right)^2 }, \sqrt{ k \cdot \left(\frac{1}{3}\right)^2 + (n-k) \cdot \left(\frac{2}{3}\right)^2 } \right)$$

Which is $$\frac{ \sqrt{\min( n + 3k, 4n -3k ) }}{3}$$

Since, both terms groths and shrink linearly, this minimum is maximized when $n + 3k = 4n -3k$, i.e. $3n = 6k$, that is when $k = \frac{n}{2}$. If $n$ is odd just round up or down, since, for the cube, the term in the minimum vary by the same opposite amounts, the minimum itself will yield the same result with $k$ rounded up or a rounded down.

Thus your final distance is $$R = \frac{\sqrt{n + 3\left\lfloor\frac{n}{2}\right\rfloor}}{3}$$

For the hyper-rectangle originating from $0$, you must notice that $C_1 = \frac{1}{2} C_2 = \frac{1}{3} \Delta$, with $\Delta$ the diagonal. So you have sum of squared components of $\Delta$ instead of multiplying by $k$ in the distance formula. Also be more careful with the rounding up and down when maximizing the minimums.

• Thanks for your thoughts. It seems it doesn't give the smallest possible radius $R$. For example, for the cube: $[0,1]^3$ using your approach: $R = \sqrt{ \frac{7}{9} }$ while the smallest possible actually is $\sqrt{ \frac{6}{9} }$ – Remis Mar 1 '16 at 22:56
• I must have made a mistake somewhere, I'll check. – Lærne Mar 2 '16 at 7:35
• Okay, I see it. I assumed that $3 \cdot \lfloor \frac{n}{2} \rfloor = \lfloor \frac{3n}{2} \rfloor$, which is wrong since if $n$ is odd, then $\lfloor \frac{n}{2} \rfloor = \frac{n}{2} - \frac{1}{2}$, which when multiplied by $3$ will give $\frac{3n}{2} - \frac{3}{2}$ which is different from $\lfloor \frac{3n}{2} \rfloor = \frac{3n}{2} - \frac{1}{2}$. Let me correct my answer. – Lærne Mar 2 '16 at 8:57