Dimensión VC de esferas en 3 dimensiones

9

Estoy buscando la dimensión VC del siguiente sistema establecido.

Universo tal que U R 3 . En el sistema de conjuntos R, cada conjunto S R corresponde a una esfera en R 3 de modo que el conjunto S contiene un elemento en U si y solo si la esfera correspondiente lo contiene en R 3 .U={p1,p2,,pm}UR3RSRR3SUR3

Detalles que ya sé.

  1. La dimensión VC es al menos 4. Esto se debe a que si son 4 esquinas de un tetraedro, entonces R puede romperlop1,p2,p3,p4R

  2. La dimensión VC es casi 5. Esto se debe a que el sistema establecido puede integrarse en con esferas en R 3 correspondientes a hiperplanos en R 4 . Se sabe que los hiperplanos en R d tienen dimensión VC d + 1 .R4R3R4Rdd+1

Ashwinkumar BV
fuente

Respuestas:

8

Aquí hay un argumento fácil:

Suponga que hay una serie de 5 puntos que pueden ser destrozados por las bolas. Así que para cualquier conjunto S U , existe una bola B st B U = S y una bola B ' st B 'U = U S . Por lo tanto, B B ' no contiene puntos de U . Si B B = , B y B USUBBU=SBBU=USBBUBB=BBSe puede separar por un plano. De lo contrario, la intersección de las superficies de y B ' es un círculo. El plano en el que se encuentra el círculo separa los S de U S . Por lo tanto, U puede ser destruido por medios espacios, una contradicción.BBSUSU

El mismo argumento en una dimensión superior muestra que la dimensión VC de las bolas es igual a la dimensión VC de los medios espacios.

Sasho Nikolov
fuente
Si. Me di cuenta de esta solución, pero demasiado tarde;).
Sariel Har-Peled
8

Mi solución es incorrecta Ver otra respuesta ...

Sariel Har-Peled
fuente
No, estoy incluyendo esto como ejemplo en una charla. En lugar de mencionarlo como <= 5, pensé que sería mejor anotar el número exacto. Gracias de todos modos.
Ashwinkumar BV
Supuse que no era un problema de trabajo en casa ...
Sariel Har-Peled
@Sariel: Encontré una prueba fácil. ¿Debo publicar o quieres pensar un poco más?
Sasho Nikolov el
1
Publicar como una respuesta diferente, y luego eliminaría la mía ...
Sariel Har-Peled