Planar dinâmico exato k-vizinhos mais próximos para dados patológicos

8

Quais são os resultados mais conhecidos para uma estrutura de dados que oferece as seguintes operações em conjuntos de pontos no espaço euclidiano bidimensional:

  • insert(x)
  • delete(x)
  • (onde k é um número inteiro maior que 0) retorna os k pontos mais próximos de x que estão no conjunto.nearest(k,x)kkx

Nesse caso em particular, não estou particularmente interessado no vizinho mais próximo aproximado, nos algoritmos de Monte Carlo ou nos algoritmos que assumem que os dados estão bem formados de alguma forma.

Não tenho preconceito contra os algoritmos de Las Vegas, algoritmos que assumem que as coordenadas do ponto têm bits ou algoritmos com tempo de execução dependendo de k .O(lgn)k

jbapple
fonte
Presumo que parte da entrada da consulta e não seja uma constante fixa? k
Suresh Venkat
Você assume corretamente.
Jbapple #
era disso que eu tinha medo. O problema é que, como k pode ser tanto quanto n / 2, você realmente está perguntando sobre os níveis médios de um arranjo de funções e isso pode mudar muito na inserção e exclusão.
Suresh Venkat
Ajuda se k faz parte da entrada da consulta e um parâmetro do tempo de execução? (Eu acho que isso é chamado de "sensível output-")
jbapple
f(n)+k

Respostas:

7

O()k=1O(k)k

David Eppstein
fonte