2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David K Feb 29 '16 at 14:01
  • $\begingroup$ @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. $\endgroup$ – Remis Feb 29 '16 at 14:30
  • $\begingroup$ 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. $\endgroup$ – David K Feb 29 '16 at 15:16
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think instead of the term $s_q^2$ in the sum under the radical, you want $\frac19 s_q^2$. $\endgroup$ – David K Feb 29 '16 at 13:54
  • $\begingroup$ Nicely spotted @DavidK! $\endgroup$ – N74 Feb 29 '16 at 13:56
  • $\begingroup$ @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. $\endgroup$ – Remis Feb 29 '16 at 14:56
  • $\begingroup$ @Remis. Just edited the answer. $\endgroup$ – N74 Feb 29 '16 at 16:10
  • $\begingroup$ @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. $\endgroup$ – Remis Mar 1 '16 at 20:53
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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} }$ $\endgroup$ – Remis Mar 1 '16 at 22:56
  • $\begingroup$ I must have made a mistake somewhere, I'll check. $\endgroup$ – Lærne Mar 2 '16 at 7:35
  • $\begingroup$ 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. $\endgroup$ – Lærne Mar 2 '16 at 8:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.