Uma rede para um espaço de intervalo ( X , R ) é um subconjunto N de X, de modo que N ∩ R não é vazio para todos os R ∈ R, de modo que | X ∩ R | ≥ ε | X | .
Dado um espaço de alcance da dimensão VC d , uma rede ε do tamanho O ( dpode ser calculado no tempoO(d)3d(1(veja [1], Thm 4.6).
Até que ponto o termo intrínseco a esse problema? Especificamente, pode ser melhorado para 2 O ( d ) ? Existem limites inferiores conhecidos?
Uma questão relacionada: existem condições gerais em para as quais se sabe que existe essa melhoria?
[1] Bernard Chazelle. O método da discrepância. 2000.
ds.algorithms
cg.comp-geom
vc-dimension
epsilon-nets
Don Sheehy
fonte
fonte
Respostas:
fonte