VC-Dimension von Kugeln in 3 Dimensionen

9

Ich suche nach der VC-Dimension des folgenden Set-Systems.

Universum so dass . Im Mengen-System jede Menge einer Kugel in so dass die Menge genau dann ein Element in enthält, wenn die entsprechende Kugel es enthält in .U={p1,p2,,pm}UR3RSRR3SUR3

Details, die ich bereits kenne.

  1. Die VC-Dimension ist mindestens 4. Dies liegt daran, dass wenn 4 Ecken eines Tetraeders sind, es durch zerschmettert werden kannp1,p2,p3,p4R

  2. Die VC-Dimension beträgt höchstens 5. Dies liegt daran, dass das Mengen-System in eingebettet werden kann, wobei Kugeln in den Hyperebenen in . Es ist bekannt, dass Hyperebenen in die VC-Dimension .R4R3R4Rdd+1

Ashwinkumar BV
quelle

Antworten:

8

Hier ist ein einfaches Argument:

Angenommen, es gibt eine Menge von 5 Punkten, die durch Bälle zerschmettert werden können. So für jede Menge besteht ein Ball st und eine Kugel st . Daher enthält keine Punkte von . Wenn , können und durch eine Ebene getrennt werden. Ansonsten ist der Schnittpunkt der Flächen von und ein Kreis. Die Ebene , in der der Kreis liegt trennt aus . Daher istUSUBBU=SBBU=USBBUBB=BBBBSUSU kann durch Halbräume zerschmettert werden, ein Widerspruch.

Das gleiche Argument in einer höheren Dimension zeigt, dass die VC-Dimension von Kugeln gleich der VC-Dimension von Halbräumen ist.

Sasho Nikolov
quelle
Ja. Ich habe diese Lösung erkannt, aber zu spät;).
Sariel Har-Peled
8

Meine Lösung ist falsch. Siehe andere Antwort ...

Sariel Har-Peled
quelle
Nein, ich nehme dies als Beispiel in einen Vortrag auf. Anstatt es als <= 5 zu erwähnen, dachte ich, es wäre besser, die genaue Zahl zu notieren. Trotzdem danke.
Ashwinkumar BV
Ich nahm an, dass es kein Hausarbeitsproblem war ...
Sariel Har-Peled
@ Sarah: Ich habe einen einfachen Beweis gefunden. Soll ich posten oder möchtest du noch etwas darüber nachdenken?
Sasho Nikolov
1
Poste als andere Antwort weg, und dann würde ich meine löschen ...
Sariel Har-Peled