Investigamos en internet para así tenerte la respuesta a tu dilema, si continúas con alguna inquietud puedes dejarnos tu duda y responderemos con gusto, porque estamos para servirte.
Solución:
Una solución es una aplicación de un teorema debido a Karl Menger (como alternativa, se puede usar el teorema de Schoenberg).
Para simplificar las cosas, asumiré para la mayor parte de la respuesta que los puntos $ c_1, …, c_n $ satisfacer es decir, están en “posición general”: forman el conjunto de vértices de un$ n-1 $
-simplex dimensional. (Explicaré al final de la respuesta cómo reducir el caso general a este).
Primero, permítanme describir el teorema de Menger. Menger dio un conjunto de condiciones necesarias y suficientes para un espacio métrico finito $ (X, d) $ para incrustar isométricamente en un espacio de Hilbert$ H $ ; también dio una caracterización de la menor dimensión de $ H $ en términos de la métrica$ d $ ; Denotaré este número $ h (X) $
(Estoy suprimiendo la rotación de la métrica aquí y abajo). Aquí está la solución de Menger (consulte mi respuesta aquí para obtener referencias). Dado un espacio métrico finito $ X = x_0, x_1, …, x_n $
(Estoy suprimiendo la notación de la métrica), Menger usa el siguiente determinante, también conocido como el determinante de Cayley-Menger:
$$ Delta (X) = left | begin array ccccc d (x_0, x_0) & d (x_0, x_1) & … & d (x_0, x_n) & 1 \ d (x_1 , x_0) & d (x_1, x_1) & … & d (x_1, x_n) & 1 \ vdots & vdots & … & vdots & vdots \ d (x_n, x_0) & d (x_n, x_1) & … & d (x_n, x_n) & 1 \ 1 & 1 & … & 1 & 0 end array right |. $$ La primera (y la más importante) de las condiciones de Menger es que $ Delta (X) $ tieneel signo de $ (- 1) ^ X $
sentido:
$$ Delta (X) (-1) ^ ge 0. $$ Es más, $ h (X) = k $ implica $ Delta (X) = 0 $ (y lo contrario es cierto siempre y cuando $ h (Y) = | Y | -1 $ para todos los subconjuntos adecuados$ Y subconjunto X $ ). El resto de las condiciones de Menger son inductivas: para $ X $ para incrustar isométricamente en un espacio de Hilbert, todos los subconjuntos$ Y $ de $ X $ tienen que ser incrustables en espacios de Hilbert, es decir, sus determinantes $ Delta (Y) $ tienes que tener el signo de $ (- 1) ^ Y $
(como anteriormente). Observación. Aquí hay una observación importante sobre el determinante $ Delta (X) $ considerado como una función en las variables$ d (x_0, x_1), …, d (x_0, x_n) $
: $ Delta (X) $ es un polinomio de segundo grado en estas variables, con los términos constantes iguales$ pm Delta (X_0) $ , dónde $ X_0 = X setminus x_0 $ (con la restricción de la métrica). Como polinomio de $ d (x_0, x_i) $
tiene la forma
$$ A_i d ^ 2 (x_0, x_i) + B_i d (x_0, x_i) + C_i, i = 1, …, n, $$ dónde $ A_i = Delta (X_ 0i) ne 0 $ y $ X_ 0i subconjunto X $ se obtiene de $ X $ quitando los puntos$ x_0, x_i $
). Aquí es donde estoy usando la suposición . Usaré la notación $ H $para un espacio de Hilbert de dimensión infinita, que contiene todos los espacios euclidianos $ E ^ 1 subconjunto E ^ 2 subconjunto E ^ 3 subconjunto … $ . También usaré la notación $ S (c, r) $ para denotar la esfera redonda en $ H $ centrado en $ c $y de radio
$ r $ .Dado un subconjunto $ C subconjunto H $ , dejar $ intervalo (C) $ denotar el tramo afínde $ C $ , es decir, el subconjunto afín más pequeño de $ H $conteniendo
$ C $
. Primero resolvamos un problema ligeramente diferente al tuyo: Dado un subconjunto finito $ c_1, …, c_n $en $ H $ , cuales son las condiciones necesarias y suficientes en las distancias $ d_ ij = || c_i-c_j || $y radios
$ r_i ge 0 $
, para la intersección $$ bigcap_ i = 1 ^ n S (c_i, r_i) $$ de esferas en
$ H $
no estar vacío?
El teorema de Menger proporciona una respuesta al problema de la esfera. A saber: dada una tupla $$ tau = ((c_1, r_1), …, (c_n, r_n)), $$formar un resumen espacio pre-métrico $ (X, d) = X_ tau $ igual a
$ c_0, c_1, …, c_n $
con $$ d (c_i, c_j) = d_ ij, d (c_0, c_k) = r_k, k = 1, …, n. $$ (El adjetivo pre-métrico se refiere al hecho de que $ d $podría violar las desigualdades de triángulos cuando se aplica a triples
-
$ c_0, c_i, c_j $ .) Entonces los siguientes son equivalentes: $ X_ tau $incrusta isométricamente en
-
$ H $ .
$ X_ tau $ es un espacio métrico que satisface las condiciones del teorema de Menger, es decir (a) $ d (c_i, c_k) le d (c_i, c_j) + d (c_j, c_k) $ para todos los triples
$ i, j, k in 0, …, n $
tal que el producto $$ ijk = 0. $$ (b) Para todos los subconjuntos $ Y subconjunto X_ tau $conteniendo $ c_0 $
,
$ Delta (Y) (-1) ^ ge 0 $
3.
$$ bigcap_ i = 1 ^ n S (c_i, r_i) ne conjunto vacío. $$
Es más, $$ span ( c_1, …, c_n ) cap bigcap_ i = 1 ^ n S (c_i, r_i) ne emptyset $$si y solo si, además,
$ Delta (X) = 0 $ . Tenga en cuenta también que, para cada subespacio euclidiano de dimensión finita $ A $conteniendo
$ c_1, …, c_n $
, la intersección $$ A cap bigcap_ i = 1 ^ n S (c_i, r_i) $$está vacío o es un solo punto, igual a la intersección de las esferas anteriores en el espacio de Hilbert $ H $, así como en $ intervalo ( c_1, …, c_n ) $, o es una esfera redonda de dimensión
$ dim (A) – n $
.
Ahora, vayamos al problema original de la intersección de bolas cerradas en espacios euclidianos. Es fácil ver que, si
$$ bigcap_ i = 1 ^ n S (c_i, r_i) ne conjunto vacío, $$
luego $$ span ( c_1, …, c_n ) cap bigcap_ i = 1 ^ n B (c_i, R_i) ne conjunto vacío, $$para cualquier $ n $-tuplas de números reales
$ R_i ge r_i $ . Definición. Una colección de bolas redondas. $ mathcal G = B (c_1, r_1), …, B (c_n, r_n) $ en un espacio euclidiano (posiblemente de dimensión infinita) $ E ^ alpha $ sera llamado redundante [n]si hay un subconjunto adecuado $ I subconjunto
= 1, …, n $ [n]tal que
$$ bigcap_ i in B (c_i, r_i) = bigcap_ i in I B (c_i, r_i). $$ La colección de bolas se llamará
irredundante
de lo contrario. La misma terminología se aplica a la tupla de centros y radios: $$ tau = ((c_1, r_1), …, (c_n, r_n)). $$Es fácil ver que una tupla es redundante si y solo si es redundante en
$ intervalo ( c_1, …, c_n ) $ . Si uno sabe que una tupla
$ tau $ es redundante, entonces se pueden describir las condiciones necesarias y suficientes para que no esté vacío la intersección de una colección de bolas usando una subcolección más pequeña, por lo tanto, proporcione una descripción inductiva de esta manera.Como ejemplo: para $ n = 3 $ , una tupla es redundante si y solo si el espacio pre-métrico de 4 puntos
$ (X, d) $ como arriba viola las desigualdades triangulares, es decir, no es un espacio métrico. Lema. Una tupla
$ tau = ((c_1, r_1), …, (c_n, r_n)) $
es redundante si y solo si $$ bigcap_ i = 1 ^ n S (c_i, r_i) = conjunto vacío, $$donde se toma la intersección
$ H $ . La prueba de este lema es una sencilla inducción sobre
$ n $ y lo omito. Este lema permite dar un criterio numérico de redundancia: Corolario.Suponer que
$ n ge 3 $ [n]. A menos que la intersección de bolas
$$ bigcap_ i in B (c_i, r_i) $$ está vacío, la tupla
$ tau = ((c_1, r_1), …, (c_n, r_n)) $ es irredundante si y solo si: [n](a) Para cada subconjunto adecuado$ I subconjunto
PS
, la tupla correspondiente $$ tau_I = ((c_ i_1, r_ i_1), …, (c_ i_k, r_ i_k)), I = (i_1, …, i_k) $$ es irredundante (en particular,
$ (X, d) $ es un espacio métrico).(B)
$ Delta (X) (-1) ^ n + 1 ge 0 $
. Tenga en cuenta que este corolario no resuelve directamente el problema del no vacío de la intersección de bolas. Por fin, aquí hay una respuesta al problema del no vacío de la intersección de bolas redondas. $ B (c_i, r_i) $ en $ intervalo ( c_1, …, c_n ) $(que todavía suponemos que tiene dimensión $ n-1 $). La solución es inductiva en $ n $ . Para
$ n = 2 $
la respuesta está en forma de “triángulo una desigualdad” $$ B (c_1, r_1) cap B (c_2, r_2) ne conjunto vacío $$si y solo si
$ r_1 + r_2 ge d_ 12 = || c_1-c_2 || $ .Suponga que el problema está resuelto para todos. $ m . En particular, tenemos una prueba de redundancia para conjuntos de $ m $pelotas, $ m , es decir, además del criterio numérico también podemos decir si la intersección de $ m $las bolas no están vacías. Ahora, dada una tupla
$ tau = ((c_1, r_1), …, (c_n, r_n)) $ , cualquiera: (i) Existe un subtuple adecuado
$ tau_I $
que es redundante (y que es algo que podemos probar), por lo tanto, $ tau $ en s mismo es redundante y, por tanto, el problema de la no vacuidad de $ tau $ se reduce a un juego de bolas más pequeño.
(ii) Suponga que todas las subtuplas adecuadas $ tau_I $ son irredundantes; en particular,
el subtuple $ sigma = ((c_1, r_1), …, (c_ n-1, r_ n-1)) $ es irredundante. Resuelve la ecuación $ Delta (X_ tau) = 0 $ por lo desconocido $ y = d (c_0, c_n) $; esta ecuación tiene la forma
$$ A_n y ^ 2 + B_n y + C_n = 0, $$
con $ A_n ne 0 $, dónde $ A_n, B_n, C_n $ son funciones de la tupla $ sigma $. Esta ecuación cuadrática tiene dos soluciones (posiblemente iguales)
$$ y_ pm = – frac B_n 2A_n pm sqrt left ( frac B_n 2A_n right) ^ 2 – C_i. $$
Ambas soluciones son reales y no negativas. Geométricamente hablando, corresponden a lo siguiente:
Considere la intersección de esferas en $ intervalo ( c_1, …, c_n ) $:
$$ bigcap_ i = 1 ^ n-1 S (c_i, r_i) = S ^ 0. $$
Esta intersección no está vacía (¡por el supuesto de irredundancia!) Y es un singleton (contenido en $ intervalo ( c_1, …, c_ n-1 ) $) o es un conjunto de 2 puntos $ s_-, s _ + } $, uno de sus puntos $ s _- $ está más cerca de $ c_n $ que el otro. Luego
$$ y_ pm = || c_n – s _ pm ||. $$
El caso cuando $ S ^ 0 $ es un singleton ocurre precisamente cuando $ y _ + = y _- $. Luego
begin ecuación bigcap_ i = 1 ^ n B (c_i, r_i) ne conjunto vacío, end ecuación
si y solo si $ r_n ge y _- $, es decir, ya sea $ Delta (X_ tau) (-1) ^ n ge 0 $ o la tupla $ tau $ es redundante porque
$ B (c_n, r_n) $ contiene estrictamente la intersección
begin ecuación bigcap_ i = 1 ^ n-1 B (c_i, r_i). end ecuación
Como ejemplo, aquí está esta solución implementada en el caso de la intersección de tres bolas en el plano euclidiano,
$ tau = ((c_1, r_1), …, (c_3, r_3)) $. Usaré la notación
$$ d_ ij = || c_i-c_j || $$
-
Pruebe los subtuples adecuados para el vacío: si para algunos $ 1 le i$$ r_i + r_j
luego $ B (c_i, r_i) cap B (c_j, r_j) = conjunto vacío $ y hemos terminado. Supongamos, por tanto, que todas estas intersecciones no están vacías. -
Pruebe las subtuplas adecuadas para determinar la redundancia: si para algunos $ 1 le i ne j le 3 $$$ r_i> r_j + d_ ij $$
entonces podemos eliminar la bola $ B (c_i, r_i) $ de la colección $ B (c_k, r_k), k = 1,2,3 $ sin cambiar la intersección y, por lo tanto, la no vacuidad de la triple intersección está garantizada por la desigualdad del triángulo
$$ r_k + r_j ge d_ jk, i notin j, k , j ne k. $$ -
Supongamos, por último, que $ X_ tau $ es un espacio métrico y cada subtuple adecuado $ sigma $ en $ tau $
es irredundante. Luego
begin ecuación bigcap_ i = 1 ^ 3 B (c_i, r_i) ne emptyset, end ecuación
si y solo si $ r_3 ge y _- $, dónde $ y _- $ es la raíz más pequeña del polinomio
$$ A_3 y ^ 2 + B_3 y + C_3. $$
Los coeficientes $ A_3, B_3, C_3 $ se calculan de la siguiente manera:
$$ A_3 = 2 d_ 12, $$$$ B_3 = -2r_1 (d_ 12 + d_ 23 -d_ 13) – 2r_2 (d_ 31 + d_ 12 -d_ 23), $$$$ C_3 = Delta (X_0) = left | begin array cccc 0 & d_ 12 & d_ 13 & 1 \ d_ 21 & 0 & d_ 23 & 1 d_ 31 & d_ 32 & 0 & 1 \ 1 & 1 & 1 & 0 end array right |. $$
Por último, déjame explicarte la solución para $ n $ puntos en $ H $, que no están en posición general, es decir, su intervalo afín tiene dimensión $ le n $. Una vez más, tomaré una solución para PS puntos por sentado. Entonces, de acuerdo con el teorema de Haley,
$$ bigcap_ i in [n] B (c_i, r_i) ne conjunto vacío $$
si y solo si para cada subconjunto adecuado $ I subconjunto [n]PS,
$$ bigcap_ i in I B (c_i, r_i) ne conjunto vacío. $$
El problema de la intersección para $
valoraciones y reseñas
Finalizando este artículo puedes encontrar las anotaciones de otros sys admins, tú igualmente tienes el poder mostrar el tuyo si dominas el tema.