Dimensão VC de esferas em 3 dimensões

9

Estou pesquisando a dimensão VC do seguinte sistema definido.

Universo tal que U R 3 . No sistema de conjuntos R, cada conjunto S R corresponde a uma esfera em R 3, de modo que o conjunto S contém um elemento em U se e somente se a esfera correspondente o contém em R 3 .U={p1,p2,,pm}UR3RSRR3SUR3

Detalhes que eu já sei.

  1. A dimensão VC é pelo menos 4. Isso ocorre porque se são 4 cantos de um tetraedro, então ele pode ser quebrado por Rp1,p2,p3,p4R

  2. A dimensão VC é no máximo 5. Isso ocorre porque o sistema definido pode ser incorporado em com esferas em R 3 correspondentes a hiperplanos em R 4 . Sabe-se que hiperplanos em R d tem VC-dimensão d + 1 .R4R3R4Rdd+1

Ashwinkumar BV
fonte

Respostas:

8

Aqui está um argumento fácil:

Suponha que haja um conjunto de 5 pontos que podem ser quebrados por bolas. Assim, para qualquer conjunto S L , existe uma bola B r B U = S e uma bola B ' r B 'L = L S . Portanto, B B ' não contém pontos de U . Se B B = , B e B USUBBU=SBBU=USBBUBB=BBpode ser separado por um plano. Caso contrário, a interseção das superfícies de e B é um círculo. O plano em que os círculos mentiras separa S de L S . Portanto, U pode ser quebrado por meios espaços, uma contradição.BBSUSU

O mesmo argumento na dimensão superior mostra que a dimensão VC das bolas é igual à dimensão VC dos meiosespaços.

Sasho Nikolov
fonte
Sim. Percebi essa solução, mas tarde demais;).
precisa saber é o seguinte
8

Minha solução está incorreta. Veja outra resposta ...

Sariel Har-Peled
fonte
Não, estou incluindo isso como exemplo em uma palestra. Em vez de mencioná-lo como <= 5, pensei que seria melhor anotar o número exato. Obrigado de qualquer forma.
Ashwinkumar BV
Eu achava que não era um problema homeowork ...
Sariel Har-Peled
@Sariel: Encontrei uma prova fácil. Devo postar ou você quer pensar um pouco mais?
Sasho Nikolov
11
Postar afastado como uma resposta diferente, e então eu iria apagar o meu ...
Sariel Har-Peled