я есть список L из ~ 30k местоположений (записанных как пары долгота / широта) и список E из ~ 1 м событий (с местоположениями, записанными как пары долгота / широта), каждое из которых происходит в точке в L. Я хочу помечать каждое событие в E соответствующим местоположением в L. Но координаты в L и E округляются по-разному - от E до пяти знаков после запятой, от L до 13 - так что якобы идентичные координаты могут фактически отличаться на ~ 10 ^ -5 градусов, или ~ 1 метр (Точки в L разделены не менее чем на ~ 10 м.)

Таким образом, мне нужна ближайшая точка в L к каждой точке E; очевидный алгоритм грубой силы O (| L || E |) слишком медленный. L достаточно мала по сравнению с E, поэтому алгоритмы, которые предварительно обрабатывают L и амортизируют время предварительной обработки над E, хороши. Это хорошо изученная проблема? Ссылки, которые я могу найти, предназначены для связанных, но различных задач, таких как нахождение минимального расстояния между парой точек в одном наборе.

Возможно актуально:Диаграммы ВороногоХотя я не понимаю, как предварительная обработка L в диаграмме Вороного сэкономила бы мне вычислительное время.