Wymiar VC komórek Voronoi w R ^ d?

Załóżmy, że mam punktów w . Indukują one diagram Voronoi. Jeśli przypiszę do każdego z punktów etykietę , wywołają one funkcję binarną na . Pytanie: jaki jest wymiar VC wszystkich takich możliwych funkcji binarnych indukowanych przez niektóre punkty i pewne oznakowanie tych punktów? $k$ $\mathbb{R}^d$ $k$ $\pm$ $\mathbb{R}^d$ $k$

— Aryeh
źródło

Widzę, że granica

O (d k^{2} \log k)

$O(dk^2\log k)$ jest podana w Twierdzeniu 1 . Czy to najlepiej znany?

— Aryeh

Sprawdź Twierdzenie 21.5, rozdział 21 w książce „A probabilistyczna teoria rozpoznawania wzorców (1996)” Devroye, Gyorfi i Lugosi. Myślę, że obowiązuje następująca górna granica: VC $\leq$ $k + (d+1)k^2\log k$ .

— użytkownik2798850
źródło

Co tu jest ?

n

$n$

— Sasho Nikolov

Modulo the mystery , wydaje się, że jest tego samego rzędu wielkości, jak cytowałem powyżej.

n

$n$

— Aryeh