Dimensão VC de células Voronoi em R ^ d?

9

Suponha que eu tenha pontos em . Isso induz um diagrama de Voronoi. Se eu atribuir a cada um dos pontos um rótulo , eles induzirão uma função binária em . Pergunta: qual é a dimensão VC de todas essas funções binárias possíveis induzidas por alguns pontos e alguma rotulagem desses pontos?kRdk±Rdk

Aryeh
fonte
Vejo que um limite de é dado no Teorema 1 . Isso é o mais conhecido? O(dk2registrok)
Aryeh

Respostas:

1

Por favor, verifique o Teorema 21.5, Seção 21 do livro "Uma teoria probabilística do reconhecimento de padrões (1996)" de Devroye, Gyorfi e Lugosi. Eu acho que o seguinte limite superior é válido: VC . k+(d+1 1)k2registrok

user2798850
fonte
O que é aqui? n
Sasho Nikolov
2
Módulo o mistério , parece ser a mesma ordem de magnitude que citei acima. n
Areyh #