Этот быстрый и грязный подход может избавить вас от некоторого горя: разделите поверхность земли на блоки по 1 градусу. После этого у вас будет массив элементов размером 180x360, и вам нужно будет выполнить поиск только в небольшом количестве блоков, включая блок, содержащий новую точку, и все поля, расположенные непосредственно вокруг нее, для которых один из углов находится в пределах указанного пользователем расстояния. Вы обнаружите, что есть некоторые приемы, которые вы можете использовать, чтобы быстро выяснить, какие коробки использовать, не рассматривая их все. Только не забывайте широту и долготу.
Если у вашего «только» есть миллионы очков, и они не сгруппированы в горячие точки, это может помочь вам.
Теоретически превосходный способ: вы можете отобразить каждую точку в трехмерном пространстве и затем сохранить их в октрее , что позволит вам быстро найти близлежащие точки с произвольным расстоянием. Конечно, расстояние в трехмерном пространстве будет немного отличаться от расстояния по большому кругу на земном шаре, поэтому вам придется рассчитать коэффициент пересчета. Это должно быть просто, хотя. Вы не упоминаете язык реализации, но почти наверняка будет хорошо протестированная реализация octree для любого языка, на котором вы работаете. Если вы не против вставить сторонний код, это решение является способом идти.