минимальное расстояние между 2 точками в с ++

Question

Мне дано m мест (x, y координаты).

У меня есть n запросов на поиск ближайшего места к заданной точке P (x, y); (Минимальное евклидово расстояние)

Как я могу решить эту проблему ниже O (n * m), где n - количество запросов, а m - количество мест? Я мог бы использовать евклидово расстояние в квадрате, но оно все равно n * m.

Answer 1

Попробуйте kd-дерево .Высокопроизводительную библиотечную реализацию можно найти здесь .

Примечание: я указываю вам приблизительный поиск ближайших соседей, который оптимизирован для больших размеров.Это может быть немного излишним для вашего приложения.

Редактировать:

Для дерева 2d kd время сборки будет O (m * log (m))и время запроса будет O (n * sqrt (м)).Это должно закончиться тем, что станет чистым выигрышем над наивным решением, если число ваших запросов n превышает log (m).

Библиотека означает, что вам не нужно реализовывать ее, поэтому сложность не должна бытьпроблема.

Если вы хотите обобщить чрезвычайно быстрые запросы в большой размер, проверьте хеширование с учетом локальных особенностей .

Answer 2

Проблема ближайшего соседа , а?Я нашел книгу Роберта Седжвика Std очень полезной в этих случаях.Он описывает Поиск ближайшего соседа тоже.

Answer 3

Интересно.Чтобы уменьшить влияние n, мне интересно, возможно ли это поможет сохранить результат каждого запроса при его обработке и обработке.Умная таблица результатов может сократить необходимость вычисления sqrt (x ² + y ² ) при решении последующих запросов.