Cubrir completamente un hiper-rectángulo por dos discos congruentes ( $n$ -bolas) y encontrar el radio de las mismas

Question

Quiero encontrar una forma general de calcular el radio más pequeño posible ( $R$ ) de dos congruentes $n$ -discos ( $n$ -bolas) con los centros ( $C_1$ ) y ( $C_2$ ) que se encuentra en la diagonal del hiper-rectángulo y lo cubre completamente. Las posiciones de ambos centros son fijas y divide la diagonal principal en tres partes iguales. Ejemplos de este tipo de recubrimiento para $n = 2$ y $n = 3$ casos (para simplificar estoy usando allí $n$ -cubo, pero podría ser cualquier hiper-rectángulo) se muestran en las imágenes siguientes.

Por el momento, parece que sería posible encontrar todas las distancias entre todos los vértices del rectángulo $ V(Rect) = \{ v_i: i=1,\dots,2^n \} $ y estos dos puntos centrales $C_1$ y $C_2$ y luego a tomar: $$ R = \max_{v_i \in V(Rect)} \left\{ \min \left\{ \left\| v_i - C_1 \right\|, \left\| v_i - C_2 \right\| \right\} \right\}, $$ Sin embargo, como el número de vértices $2^n$ aumentan rápidamente cuando $n$ sube, me gustaría derivar una forma más sencilla de encontrar $R$ . Por ejemplo, considerando sólo las longitudes de los lados de los hiper-rectángulos en cada dimensión.

cobertura-2D

cobertura-3D

Answer 1

Pongamos un vértice del hiper-rectángulo en $O$ el lado opuesto será $V_{far}=(s_1, s_2,..., s_n)$ , donde $s_i$ es la longitud del lado en el $i_{th}$ dimensión.

Llamemos a $q$ el índice donde $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} $$

EDITAR. Cómo he derivado esta expresión.

En primer lugar, supongamos que $q=n$ Esto, obviamente, no tendrá ninguna repercusión en el resultado final.

Corta el hipercubo en el plano perpendicular a la diagonal. Tendrás que los puntos más alejados de $O$ son los que se encuentran al otro lado del plano y, para todos ellos, el $n_{th}$ coordenada no es $0$ . Estos puntos estarán más cerca de $C_2$ .

Ahora debemos encontrar una hiperesfera que contenga todos los puntos con el $n_{th}$ coordenadas $=0$ . Esto es fácil, ya que tenemos el centro $C_1\equiv V_{far}/3$ y el punto más lejano (en nuestro lado del corte) es $P\equiv (s_1, s_2,..., s_{n-1},0)$ .

Así que con el teorema de Pitágoras el resultado se obtiene fácilmente.

Hay que tener en cuenta que este es el radio mínimo dada la posición de $C_1$ . Si se permite mover este punto se pueden encontrar radios más pequeños.

Answer 2

A continuación sólo se considera el caso de un cubo.

Dejemos que $C:=[{-1},1]^n$ sea el cubo y $c_\pm:=\pm{1\over3}(1,1,\ldots,1)$ los dos centros de prospección. El plano $x_1+x_2+\ldots x_n=0$ divide $C$ en dos mitades $$C_+:=\bigl\{x\in C\bigm| x_1+x_2+\ldots+x_n\geq0\bigr\}$$ y $C_-:=-C_+\>$ . Los puntos en $C_+$ se encuentran más cerca de $c_+$ por lo que deben ser cubiertos por la esfera centrada en $c_+$ . De ello se desprende que tenemos que encontrar $$\max\left\{\sum_{k=1}^n\left(x_k-{1\over3}\right)^2\biggm| x\in C_+\right\}\ .$$ Considere un punto $x\in C_+$ y suponer que $$-1<x_1\leq x_2<1\ .$$ Poner $\delta:=\min\{x_1-(-1), 1-x_2\}$ y reemplazar $x_1$ , $x_2$ por $$x_1':=x_1-\delta,\qquad x_2':=x_2+\delta\ .$$ Entonces $x_1'=-1$ o $x_2'=1$ y $x_1'+x_2'=x_1+x_2$ . De ello se desprende que $x':=(x_1',x_2',x_3,\ldots, x_n)\in C_+$ . Desde $$\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$$ se deduce que la función objetivo $\phi$ ha aumentado estrictamente con la sustitución $x\rightsquigarrow x'$ .

Esto permite sacar la siguiente conclusión: Los puntos óptimos factibles tienen como máximo $1$ coordenadas $\ne\pm1$ por lo que se puede escribir en la forma $$x=\bigl((-1)^r,(+1)^{n-1-r},t\bigr)$$ con $0\leq r\leq n-1$ y $-1\leq t\leq1$ . Dado que cada entrada $-1$ añade ${16\over9}$ a $\phi$ , mientras que a $+1$ sólo añade ${4\over9}$ queremos $r$ lo más grande posible. Si $2r>n$ entonces $$\sum_{k=1}^n x_k=-r+(n-1-r) +t<t-1<0\ ,$$ lo cual está prohibido. Parece que $r:=\lfloor n/2\rfloor$ y $t=1$ es óptimo, si $n$ es par o impar.

Answer 3

Voy a ir al grano con el $[0,1]^n$ cubo. Su puede adaptarse para un hiper-rectángulo. Sus centros se encuentran en la diagonal. Así, $C_1 = (c_1,c_1, ..., c_1)$ y $C_2 = (c_2,c_2, ..., c_2)$ .

Para $C_i$ la distancia con un vértice $v$ es $$ \sqrt{ (c_i-v_1)^2 + (c_i-v_2)^2 + ... + (c_i-v_n)^2 } $$

Por construcción, el $v_j$ son $0$ y $1$ . Por lo tanto, si $v$ tiene $k$ y $n-k$ ceros, la fórmula es $$ \sqrt{ k \cdot (1-c_i)^2 + (n-k) \cdot c_i^2 } $$

Así, en su fórmula, cada mínimo es en realidad : $$ \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) $$

Desde $c_1 = \frac{1}{3}$ y $c_2 = \frac{2}{3}$ esto es: $$ \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) $$

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

Dado que ambos términos crecen y se reducen linealmente, este mínimo se maximiza cuando $n + 3k = 4n -3k $ es decir $3n = 6k$ Es decir, cuando $k = \frac{n}{2}$ . Si $n$ es impar sólo redondear hacia arriba o hacia abajo, ya que, para el cubo, el término en el mínimo varían en las mismas cantidades opuestas, el propio mínimo dará el mismo resultado con $k$ redondeado hacia arriba o hacia abajo.

Por lo tanto, su distancia final es $$ R = \frac{\sqrt{n + 3\left\lfloor\frac{n}{2}\right\rfloor}}{3} $$

Para el hiper-rectángulo que se origina en $0$ , debe notar que $C_1 = \frac{1}{2} C_2 = \frac{1}{3} \Delta$ con $\Delta$ la diagonal. Así que tienes la suma de los componentes al cuadrado de $\Delta$ en lugar de multiplicar por $k$ en la fórmula de la distancia. También hay que tener más cuidado con el redondeo hacia arriba y hacia abajo al maximizar los mínimos.