Classificando por distância euclidiana

$S$ é um conjunto de pontos em um plano. Um ponto aleatório é dado no mesmo plano. A tarefa é classificar todos pela distância euclidiana entre e . $x \notin S$ $y \in S$ $x$ $y$

Uma abordagem sem cérebro é calcular as distâncias entre e para todos os e depois classificá-las usando qualquer algoritmo rápido. $x$ $y$ $y \in S$

Existe alguma maneira de armazenar ou pré-processar para que o processo de classificação se torne mais rápido? $S$

cg.comp-geom sorting Alex K.
fonte

Você pode considerar uma grade de tamanho apropriado e pontos de grupo pelo quadrado correspondente (usando, digamos, tabela de hash). Então, para certos pares de quadrados, é possível inferir que todos os pontos de um quadrado estão mais longe de que todos os pontos de outro quadrado. Na prática, isso poderia ajudar, eu acho.

x

$x$

Ilyaraz #

A “abordagem sem cérebro”, que você declarou, funciona em O (n log n), onde n é o número de pontos em S, que eu acho que é bastante rápido na prática. Deseja eliminar o fator log n ou deseja outra coisa, como classificação externa ?

Tsuyoshi Ito

O ponto é que eu tenho praticamente tempo ilimitado para preparar meu conjunto de pontos, mas o tempo para classificá-los é muito limitado. Dito isto, qualquer aceleração da classificação padrão é apreciada - mesmo que seja o mesmo O (n log n), mas mais rápido no pior dos casos (ou melhor, ou o que seja).

Alex K.

Por exemplo, se eu armazenar S como uma árvore em 2-d, posso encontrar um vizinho mais próximo no tempo O (log n). Talvez haja uma solução semelhante para minha tarefa. Eu não sou um grande especialista em estruturas de dados espaciais - e há muitas delas - eu poderia facilmente sentir falta.

Alex K.

Respostas:

Solução 1: Encontre os bissetores perpendiculares entre pares de pontos e construa o arranjo dessas linhas. A organização possui células , nas quais a ordem classificada é constante. Portanto, crie uma estrutura de dados de localização de pontos para a organização e decore cada célula com a ordem classificada que será retornada para os pontos dentro dessa célula. As ordens classificadas entre células adjacentes diferem apenas em uma única transposição, portanto, você pode usar uma estrutura de dados persistente para permitir que as representações dessas ordens classificadas compartilhem espaço. O espaço total é e o tempo de consulta é . $\Theta(n^2)$ $\Theta(n^4)$ $O(n^4)$ $O(\log n)$

Solução 2: Escolha uma amostra aleatória de desses mesmos bissetores perpendiculares, construa seu arranjo e divida cada célula de arranjo por segmentos de linha verticais através de cada cruzamento de duas linhas amostradas. A partição resultante possui células , cada uma das quais com alta probabilidade é atravessada por bissetores não amostrados. Decore cada célula da partição com uma ordenação ordenada válida dos pontos, conforme visualizado em algum x dentro da célula. O espaço total é . $\Theta(n)$ $\Theta(n^2)$ $O(n)$ $O(n^3)$

Agora, para fazer uma consulta, localize o ponto de consulta na partição, procure a ordem armazenada com a célula da partição e use o algoritmo de classificação por comparação de árvore cartesiana de Levcopoulos & Petersson (1989) começando com essa ordem armazenada. O tempo para esta etapa é proporcional a que é o número de pontos que estão fora de ordem com o ponto . Mas é (cada bissetor não amostrado causa no máximo um par de pontos fora de ordem), portanto, o tempo de consulta também é . $\sum_i O(1+\log k_i)$ $k_i$ $y_i$ $\sum k_i$ $O(n)$ $\sum_i O(1+\log k_i)$ $O(n)$

David Eppstein
fonte

PS aqui está uma variante alternativa de solução 2, que usa o mesmo espaço e consulta tempo, mas comércios fora de um algoritmo de pré-processamento mais complicado para um algoritmo de consulta mais simples: 11011110.livejournal.com/233793.html

David Eppstein

Por que pré-processamento quando você pode classificar todos os pontos de partida no tempo e armazenar os resultados em uma tabela de hash usando o espaço para pesquisa constante?

n^{4}

$n^4$

n

$n$

O (n^{2} \log n)

$O(n^2\log n)$

O (n^{2})

$O(n^2)$

Dave

Como existem pontos de partida com diferentes ordens de classificação, não .

Θ (n^{4})

$\Theta(n^4)$

Θ (n^{2})

$\Theta(n^2)$

David Eppstein

Você provavelmente não será capaz de se afastar do tempo da maneira que o cortar; mesmo regiões pré-computadas correspondentes a todas as ordens de classificação possíveis poderiam (acredito) produzir regiões e, assim, encontrar 'sua' região por qualquer técnica de pesquisa significativa levará hora. ( EDIT: $n\log(n)$ $O(n!)$ $O(\log(n!)) = O(n\log(n))$ isso está absolutamente errado; veja excelente resposta de David Eppstein para mais informações) Uma forma útil de começar a reduzir a complexidade, por outro lado - especialmente se você não precisa o tipo completo de uma só vez, mas só precisa ser capaz de puxar aleatoriamente th-mais próximo em tempo real - pode ser através de diagramas de Voronoi de ordem superior: extensões da célula Voronoi padrão que acomodam não apenas o vizinho mais próximo, mas o segundo mais próximo etc. O artigo de Frank Dehne sobre o k-vizinho mais próximo pesquisando, http: //people.scs .carleton.ca / ~ dehne / publicações / 2-02.pdf parece ser a referência canônica; sua página inicial em http://www.dehne.carleton.ca/publications tem vários outros artigos sobre diagramas de Voronoi que podem ser úteis. $k$

Steven Stadnicki
fonte

Θ (n^{4})

$\Theta(n^4)$

O (n!)

$O(n!)$

Θ (n^{2})

$\Theta(n^2)$

@ David Acho que você deve fazer disso uma resposta.

James King

Destacado - n! parecia errado enquanto eu escrevia, mas não conseguia ver um caso contra. Vou alterar minha resposta em breve para corrigir isso, mas eu realmente gostaria de ver uma resposta mais diretamente informada; obrigado!

Steven Stadnicki