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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.