Estrutura de dados eficiente para a distância eclidiana mais próxima

Question

A questão é inspirada no seguinte problema da UVA: https : //onlinejudge.org/index.php? opção= OnlineJudge & itemID= 99999999 & Category= 18 & Página= show_problem & problema= 1628 .

.

Uma rede de estações autônomas, alimentadas por baterias, as estações de aquisição de dados foram instaladas para monitorar o clima da região da Amazon. Uma estação de despacho de pedido pode iniciar a transmissão de instruções para as estações de controle para que eles alterem seus parâmetros atuais. Para evitar sobrecarregar a bateria, cada estação (incluindo a estação de despacho de pedido) só pode transmitir duas outras estações. Os destinatários de uma estação são as duas estações mais próximas. Em caso de sorteio, o primeiro critério é escolhido o mais ocidental (mais à esquerda no mapa), e o segundo critério é escolher o mais meridional (mais baixo no mapa). Você é comissionado pelo governo do estado da Amazon para escrever um programa que decide se, dada a localização de cada estação, as mensagens podem alcançar todas as estações.

O algoritmo ingênuo, claro, construiria um gráfico com estações como vértices e calculará as bordas de um determinado vértice pesquisando em todos os outros vértices para os dois mais próximos. Então, poderíamos simplesmente correr DFS / BFS. Claro, isso leva $ o (v ^ 2) $ tempo para construir o gráfico (que passa os casos de teste). Minha pergunta, no entanto, é se podemos construir o gráfico mais rápido com uma estrutura de dados apropriada. Especificamente, dado um ponto de consulta arbitrário $ P $ e um determinado conjunto de pontos $ s $ , podemos Organize os pontos em $ S $ De tal maneira que podemos encontrar rapidamente os dois pontos mais próximos em $ S $ para $ P $ (digamos, em $ \ log v $ tempo?).

Answer 1

Se eu entender isso corretamente, a maioria dos índices espaciais poderá ser usada.

Índices espaciais normalmente têm cerca de $ o (log {v}) $ tempo de inserção e tempo de pesquisa semelhante para os vizinhos mais próximos. Claro que você pode criar um diagrama voronoi disso, mas também pode usar o índice diretamente para encontrar os vizinhos mais próximos sempre que precisar deles.

para baixa dimensionalidade (2D, 3D), as famílias comuns de índices espaciais são KD-árvores (bastante simples e geralmente bom, mas tendem a ter problemas com clusters densos de pontos), Quadtrees (um pouco mais difícil de se implementar porque a precisão numérica pode ser complicada) e r-árvore (mais difícil de implementar, mas dar melhor desempenho garantido, especialmente a árvore R * (r-star-tree)).

no caso de você estar usando C ++, dê uma olhada em libspatialIndex ou o Boost R-árvore . Se você estiver usando o Java, dê uma olhada no meu Tinspin biblioteca.

O termo técnico para isso é " $ k $ perguntas mais próximas" ou " $ k $ -Nn consultas ", com $ k $ referindo-se ao número de vizinhos mais próximos que você deseja encontrar.

Answer 2

Parece que a estrutura de dados relevante pode ser uma dinâmica Diagrama Voronoi .

Os diagramas Voronoi são frequentemente a resposta quando um conjunto de pontos no avião está envolvido.

Neste caso, já que o conjunto de pontos está evoluindo, você quer uma versão dinâmica.