VC-измерение сфер в 3-х измерениях

9

Я ищу VC-размерность следующей заданной системы.

вселенная U={p1,p2,,pm} такой, что UR3, В заданной системеR каждый набор SR соответствует сфере в R3 такой, что множество S содержит элемент в U если и только если соответствующая сфера содержит ее в R3,

Детали, которые я уже знаю.

  1. VC-размерность по крайней мере 4. Это потому, что если p1,p2,p3,p4 4 угла тетраэдра, то он может быть разрушен R

  2. VC-размерность - максимум 5. Это потому, что заданная система может быть встроена в R4 с шарами в R3 соответствующие гиперплоскости в R4, Известно, что гиперплоскости вRd иметь VC-размерность d+1,

Ашвинкумар Б.В.
источник

Ответы:

8

Вот простой аргумент:

Предположим, что есть набор U5 очков, которые могут быть разбиты шариками. Так что для любого набораSUсуществует шар B улица BU=S и мяч B улица BU=US, Следовательно,BB не содержит точек U, ЕслиBB=, B а также Bможет быть разделен плоскостью. В противном случае пересечение поверхностейB а также Bэто круг. Плоскость, в которой лежит круг, отделяетсяS от US, Следовательно,U могут быть разбиты полупространства, противоречие.

Тот же аргумент в более высокой размерности показывает, что VC-размерность шаров равна VC-размерности полупространств.

Сашо Николов
источник
Да. Я понял это решение, но слишком поздно;).
Сариэль Хар-Пелед
8

Мое решение неверно. Смотрите другой ответ ...

Сариэль Хар-Пелед
источник
Нет, я включаю это в качестве примера в разговоре. Вместо того, чтобы упоминать это как <= 5, я подумал, что было бы лучше отметить точное число. В любом случае спасибо.
Ашвинкумар Б.В.,
Я предположил, что это не проблема homeowork ...
Сариэль Хар-Пелед
@Sariel: я нашел простое доказательство. Должен ли я опубликовать или вы хотите подумать еще?
Сашо Николов
1
Опубликовать как другой ответ, и тогда я бы удалил свой ...
Сариэль Хар-Пелед