Eu tenho uma lista L de ~ 30k locais (escritos como pares de longitude / latitude) e uma lista E de ~ 1m eventos (com locais escritos como pares de longitude / latitude), cada um dos quais ocorre em um ponto em L. marque cada evento em E com sua localização correspondente em L. 1 metro. (Os pontos em L são separados por pelo menos 10 m.)

Portanto, preciso do ponto mais próximo em L para todos os pontos de E; o óbvio algoritmo de força bruta O (| L || E |) é muito lento. L é pequeno o suficiente em comparação com E, pois os algoritmos que pré-processam L e amortizam o tempo de pré-processamento sobre E são bons. Esse é um problema bem estudado? Os links que encontro são para problemas relacionados, mas distintos, como encontrar a distância mínima entre um par de pontos em um conjunto.

Possivelmente relevante:Diagramas de Voronoi, embora eu não possa ver como o pré-processamento de L em um diagrama de Voronoi me pouparia tempo computacional.