У нас есть список пар х, у. Каждая пара представляет точку на двумерном пространстве. Я хочу найти ближайшую точку из этого списка, к определенной точке xq, yq. Какой алгоритм критичен по производительности для этой проблемы? Лисп очков не собирается меняться; Это означает, что мне не нужно выполнять вставку и удаление. Я хочу просто найти ближайшего соседа целевой точки xq, yq в этом наборе.

Редактировать 1: Спасибо всем! Как правильно предположил Stephan202, я хочу сделать это несколько раз; как функция. Список не обязательно отсортирован (на самом деле я не понимаю, как его можно отсортировать? Как таблица с первичным ключом из 2 столбцов a и y? Если это поможет, то я его отсортирую).

Я создам структуру данных на основе списка один раз, а затем я буду использовать эту сгенерированную структуру данных в функции (если этот процесс сам по себе уместен).

Спасибо, Джейкоб; Кажется, что структура данных KD-Tree является хорошим кандидатом для ответа (и я чувствую, что это так. Я буду обновлять, когда получу некоторые релевантные результаты).

Редактировать 2: Я обнаружил, что эта проблема называется "ближайший сосед"!

Редактировать 3: Первый заголовок был «В поисках алгоритма (для пространственных запросов и пространственного индексирования) (ближайший сосед)»; Я выбрал новое название: «Лучший алгоритм, критичный к производительности для решения ближайшего соседа». Поскольку я не хочу выполнять операции вставки и удаления моих исходных данных и хочу, чтобы только один из них был ближе к новой точке (которая не будет вставлена), я решил (в настоящее время) работать с KD-Trees. Спасибо всем!