Subconjuntos de un conjunto de puntos que se encuentran en la misma esfera

Question

Supongamos que tengo un conjunto finito $\mathcal{P} := \{x_1, x_2, \ldots , x_n\} \subset \mathbb{R}^d$.

Es allí cualquier manera de caracterizar las parejas $(x_i, x_j)$ tal de que no existe una bola de $B$$x_i, x_j \in B$, pero todos los otros puntos en $\mathcal{P}$ no están dentro de $B$.

Algunos obvios comentarios sobre la pregunta :

$\bullet$ Para cualquier punto de $x_i$, tome el punto de $x_j$ que es la más cercana a $x_i$, $(x_i, x_j)$ verifica la propiedad deseada.

$\bullet$ Durante un par $(x_i, x_j)$, si existe un $x_k$ sobre el segmento que une los dos puntos, a continuación, $(x_i, x_j)$ puede verificar la propiedad.

$\bullet$ También parece que los bordes entre "adyacente extremal puntos de la convex hull" (no sé cómo llamar a estos) siempre satisfacen la propiedad, como podemos tomar una esfera con un centro de lejos.

Esto demuestra que esta propiedad no es realmente trivial. He hecho un pequeño aproximado de la figura en el plano de aquí, con los bordes verdes representan los bordes de la satisfacción de mi problema (sólo tengo una herramienta de dibujo online disponible :) ):

Me alegro mucho de que sea necesario y/o condición suficiente, o referencia, si este tiene un nombre. Por supuesto, una respuesta parcial en el avión sería bueno ya.

Mi mayor objetivo es conseguir que una condición necesaria y suficiente para la misma propiedad, pero para más de dos puntos, y a imponer que el centro de la esfera se encuentra fuera del casco convexo de los puntos.

Answer 1

Suponiendo cerrado bolas están permitidos, $(x_i, x_j)$ tienen la propiedad si no es $x$ tal que $x_i$$x_j$, son los dos puntos más cercanos a $x$ en su conjunto, es decir, $\max(|x-x_i|, |x-x_j|) < |x-x_k|$ todos los $k \notin \{i,j\}$. Tenga en cuenta que si $x$ trabaja aquí, lo hace cualquier punto en algún barrio de $x$. Así, por simplicidad podemos restringir nuestra atención a los puntos cuyas distancias a todas las $x_j$ son distintos, es decir, el complemento de a $U$ de la unión de hyperplanes $P_{ij} = \{x: |x - x_i|=|x-x_j|\}$, $1 \le i < j \le n$. Estos hyperplanes dividen $U$ en dominios, en cada uno de los cuales los puntos $x_i$, $x_j$ se colocan en un orden fijo por sus distancias a un punto en el dominio. $(x_i, x_j)$ tienen la propiedad si al menos uno de estos dominios se $x_i$ $x_j$ como los dos primeros, en ese orden.

Answer 2

Voy a suponer que estamos trabajando en $\mathbb{R}^2,$ pero yo creo que la idea funciona en $\mathbb{R}^n$ con modificaciones.

Si $(x_i,x_j)$ verifica la propiedad de una bola de $B,$ si $B$ puede ser sustituida por otra bola de $B'$ donde $B' \subseteq B,$ $(x_i,x_j)$ también verificar la propiedad de la bola de $B'.$ Esto significa que podemos suponer que cada uno de $x_i,x_j$ se encuentra en la delimitación del círculo de $B.$ si al principio los dos son interiores a $B$ podemos disminuir el radio de $B$ manteniendo su centro fijo hasta el más alejado del centro de la $x_i,x_j$ (es decir $x_i$) se encuentra en la delimitación del círculo, y luego si $x_j$ está todavía en el interior se puede mover el centro de $B$ a lo largo del segmento de incorporarse a su centro en el límite de punto de $x_i$, mientras que el mantenimiento de la delimitación del círculo de $B$ pasando a través de $x_i$, hasta el momento en que $x_j$ también se encuentra en el borde del círculo. En tanto los cambios de la $B$ se ha trasladado a los subconjuntos de sí mismo.

Ahora considere la posibilidad de cualquier tercer punto de $x_k$ en el conjunto dado de puntos. Si sucede que $x_k$ mentiras interior para el segmento de unirse a $x_i,x_j$ $(x_i,x_j)$ no verifica la propiedad (como se señaló en el OP). En segundo lugar si $x_k$ pasa a mentir a otra parte en la línea a través de $x_i,x_j$ esto $x_k$ estará fuera de la bola de $B$, por lo que no tiene ningún efecto sobre la cuestión de si $(x_i,x_j)$ verifica la propiedad.

El cambio que necesitaba: En caso de que el círculo de delimitación de la bola de $B$ a través de $x_i,x_j,x_k$ tiene todos los otros puntos estrictamente fuera de ella, luego de que $B$ no verifica la propiedad para el par $(x_i,x_j).$ sin Embargo, desde todos los demás puntos son estrictamente positivos distancia de $B,$ el bsall $B$ puede ser ajustado ligeramente para tener $x_i,x_j$ sobre su delimitación círculo, pero hsve $x_k$ y el resto de los puntos estrictamente fuera de ella.

Ahora el resto es tedioso cálculo que se acaban de decidir de una manera u otra si el par $(x_i,x_j)$ verifica la propiedad. Para cada uno de ellos fijo $x_k$ (no en la línea a través de $x_i,x_j$) formamos el círculo a través de $x_i,x_j,x_k$ y compruebe si todos los puntos restantes en el conjunto finito se encuentran fuera del círculo. Si cualquiera de estos $x_k$ dar todo el resto de los puntos fuera de su círculo podemos parar, y decir que $(x_i,x_j)$ verifica la propiedad. Sin embargo, si ninguno de los $x_k$ ha probado todos los puntos restantes fuera de la generada círculo, podemos decir que el $(x_i,x_j)$ sí no verificar la propiedad.

Yo podría necesitar para elaborar sobre por qué el fracaso de todos los probados $x_k$ demuestra que el par $(x_i,x_j)$ no verifica la propiedad. (Va a volver a esto más adelante si puedo palabra que argumento.)