3.1 Algoritmos baseados no método logarítmico

Os primeiros algoritmos são baseados na aplicação do método logarítmico de Bentley . Esta aplicação apareceu pela primeira vez em Smid . (Veja também Schwarz .)

Agora considere a inserção de um novo ponto p. Para cada i tal que ai = 1, encontramos a célula da grade δi-grid que contém p junto com as células 3D – 1 vizinhas. Em seguida calculamos as distâncias entre p e todos os pontos de Si que estão contidos nestas células. Se encontrarmos uma distância inferior a δ, então atualizamos δ, e o par mais próximo. Resta-nos actualizar o resto da estrutura de dados. Que j seja o índice tal que a0 = a1 = … = aj – 1 e aj = 0. Que Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 e δj := δ. Construímos um δj – grade para o conjunto Sj, e descartamos as grades para o conjunto S0, S1,… Sj – 1 (tornando assim implicitamente estes conjuntos vazios).

Para provar a correção deste algoritmo, note que desde d(S) ≤ δi, basta comparar p com todos os pontos de Si que estão na vizinhança de p – na grade δi. Portanto, o par mais próximo é atualizado corretamente. Também, o novo valor Sj satisfaz d(S ∪ {p}) ≤ δj ≤ d(Sj), e para todos i > j, temos d(S ∪ {p} ≤ δi d(Si). Finalmente, a estrutura de dados atualizada contém uma grade armazenando 2i pontos para cada i tal que a representação binária de n + 1 contém um na posição i.

Analisamos a complexidade do algoritmo de inserção. Primeiro note que desde δi ≤ d(Si), a vizinhança de p no δi -grid contém, no máximo, um número constante de pontos de Si. Assim, nós gastamos O(log n) tempo para cada grade. Como a estrutura de dados contém um número logarítmico de grades, a primeira parte do algoritmo de inserção leva tempo O(log 2n).

Considerar a segunda parte do algoritmo, na qual construímos a grade δj -grid. Este passo leva tempo O(|Sj |log |Sj|), por causa da ordenação. Se guardarmos os pontos numa ordem ordenada apropriada, então esta grelha pode ser construída em tempo O(|Sj|) = O(2j). (Veja para detalhes.) Como j pode tomar qualquer valor entre zero e ⌊log n⌋, o tempo de inserção varia muito. Nós afirmamos, contudo, que o tempo amortizado para o segundo passo é limitado por O(log n).

o que prova a alegação.

Mostramos que o tempo de execução de todo o algoritmo para manter o par mais próximo é limitado por O(log 2n) tempo do pior caso mais O(log n) tempo amortizado por inserção. Usando técnicas padrão (ver Overmars ), podemos transformar a estrutura de dados de tal forma que o segundo passo leva o tempo logarítmico no pior caso. Portanto, temos uma estrutura de dados que mantém o par mais próximo no O(log 2n) pior caso de tempo por inserção. A estrutura tem tamanho O(n).

Nota que o primeiro passo do algoritmo leva tempo O(log 2n), enquanto o segundo passo leva apenas tempo O(log n). Isto sugere que uma melhoria é possível. De facto, em vez de escrevermos n no sistema de número binário, usamos o sistema de número com log n base. (Veja Overmars ou Schwarz .) Desta forma, ambos os passos levam tempo O(log 2n/log log n), enquanto o espaço usado permanece linear.

Hence, temos uma estrutura de dados de tamanho linear que mantém o par mais próximo em O(log2 n /log log n) tempo do pior caso por inserção. Note que o algoritmo usa a função floor para encontrar a célula da grade contendo o novo ponto p. Substituindo a grade por uma grade degradada, o algoritmo pode ser implementado no modelo de árvore de computação algébrica.

Ainda é possível melhorar a estrutura de dados acima. Considere novamente a estrutura de dados com base na representação de n no sistema de número binário. A observação principal é a seguinte: Se inserirmos um ponto p, então para cada i tal que ai = 1, encontramos a célula do δi -gird que contém p (mais as células vizinhas). Ou seja, realizamos consultas de localização de pontos em um número logarítmico de grades, mas sempre com o mesmo ponto de consulta p. Em Schwarz e Smid , é mostrado que a técnica de cascata fracionada pode ser estendida para que todas essas consultas juntas possam ser resolvidas no tempo O(log n log log n). O principal problema é que temos grelhas com diferentes tamanhos de grelha. Portanto, uma ordem nas células da grade tem que ser introduzida que seja “compatível” com todos estes tamanhos. Em tal ordenação é definida. Como resultado, a localização do ponto p em todas as grelhas leva a comparações O(log n). Como a ordenação é bastante complicada, no entanto, cada comparação leva tempo O(log n). No geral, obtemos uma estrutura de dados de tamanho O(n) que mantém o par mais próximo em O(log n log n) tempo amortizado por inserção. Note que precisamos da função de piso para este resultado. Isto provavelmente pode ser feito na pior das hipóteses, mas os detalhes serão enfadonhos. Não está claro se a ordenação nas células da grade também pode ser definida se usarmos grades degradadas ao invés de grades padrão.

Finalmente mencionamos uma extensão da estrutura de dados acima. A estrutura como descrita acima usa fortemente o fato de que nós só inserimos pontos. Acontece, entretanto, que a estrutura pode ser adaptada para lidar com atualizações semi-on-line, como definido por Dobkin e Suri . Uma seqüência de atualizações é chamada de semi-linha se as inserções estiverem on-line – ou seja, chegam em uma ordem desconhecida – mas quando um ponto é inserido, somos informados após quantas atualizações a partir do momento da inserção ele será apagado. Esta informação extra sobre as eliminações pode ser usada para garantir que quando um ponto é eliminado, está sempre contido numa grelha que armazena um pequeno subconjunto. Como em uma eliminação a distância mínima pode aumentar, armazenamos informações extras na estrutura de dados para atualizar o par mais próximo de forma eficiente. Desta forma, obtemos uma estrutura de dados de tamanho O(n) que mantém o par mais próximo em O(log 2n) pior tempo por atualização semicontínua. Para mais detalhes, referimos o leitor para Dobkin e Suri e Smid .