eu tenhoN dispositivos / nós móveis (digamos 100K) e eu obtenho periodicamente seus valores de localização (latitude, longitude).

Alguns dos dispositivos estão "logicamente conectados" a aproximadamenteM outros dispositivos (por exemplo, 10). Meu programa compara periodicamente a distância entre cada dispositivo e seus dispositivos conectados logicamente e determina se a distância está dentro de um limite (por exemplo, 100 metros).

Eu preciso de um algoritmo robusto para calcular essas distâncias para os dispositivos conectados logicamente.

A ordem da complexidade da abordagem da força bruta seria N * M ou Θ (N2)

O programa faz isso a cada 3 segundos (todos os dispositivos são móveis), portanto, cálculos de 100K * 10 = 3M a cada 3 segundos não são bons.

Algum bom / algoritmos clássicos para esta operação?