VC-dimensi bola dalam 3 dimensi

9

Saya mencari dimensi VC dari sistem set berikut.

Universe sedemikian rupa sehingga U R 3 . Dalam sistem himpunan R, setiap himpunan S R berkorespondensi dengan sphere dalam R 3 sehingga himpunan S mengandung elemen dalam U jika dan hanya jika sphere yang sesuai berisinya dalam R 3 .U={p1,p2,,pm}UR3RSRR3SUR3

Detail yang sudah saya tahu.

  1. Dimensi VC adalah minimal 4. Ini karena jika adalah 4 sudut tetrahedron maka dapat dihancurkan oleh Rp1,p2,p3,p4R

  2. Dimensi VC paling atas 5. Ini karena sistem yang ditetapkan dapat tertanam di dengan bola di R 3 sesuai dengan hyperplanes di R 4 . Hal ini diketahui bahwa hyperplanes di R d memiliki VC-dimensi d + 1 .R4R3R4Rdd+1

Ashwinkumar BV
sumber

Jawaban:

8

Ini argumen yang mudah:

Asumsikan ada set dari 5 poin yang dapat dihancurkan oleh bola. Jadi untuk set setiap S U , terdapat bola B st B U = S dan bola B ' st B 'U = U S . Oleh karena itu, B B ' tidak mengandung poin dari U . Jika B B = , B dan B USUBBU=SBBU=USBBUBB=BBdapat dipisahkan oleh pesawat. Kalau tidak, persimpangan permukaan dan B adalah lingkaran. Pesawat di mana kebohongan lingkaran memisahkan S dari U S . Oleh karena itu, U dapat hancur oleh halfspaces, kontradiksi.BBSUSU

Argumen yang sama di dimensi yang lebih tinggi menunjukkan bahwa dimensi VC bola sama dengan dimensi VC ruang setengah.

Sasho Nikolov
sumber
Iya. Saya menyadari solusi ini, tetapi sudah terlambat;).
Sariel Har-Peled
8

Solusi saya salah. Lihat jawaban lain ...

Sariel Har-Peled
sumber
Tidak, saya memasukkan ini sebagai contoh dalam sebuah ceramah. Daripada menyebut itu sebagai <= 5 saya pikir mungkin lebih baik untuk mencatat angka pastinya. Terima kasih.
Ashwinkumar BV
Saya berasumsi itu bukan masalah rumah tangga ...
Sariel Har-Peled
@ Sariel: Saya menemukan bukti yang mudah. Haruskah saya memposting atau Anda ingin berpikir lagi?
Sasho Nikolov
1
Posting sebagai jawaban yang berbeda, dan kemudian saya akan menghapus jawaban saya ...
Sariel Har-Peled