Поскольку вы выводите O (n ^ 2), вы не сможете стать лучше этого.
Я думаю, что это сводится к тому, насколько быстро вы можете ранжировать все остальные точки относительно расстояния доточка q.Если у вас есть структура индекса (например, KD-Tree или R-Tree), вы можете использовать дистанционный просмотр для сортировки всех остальных точек wrtq
Основная идея дистанционного просмотра заключается виметь приоритетную очередь pq, записи которой отсортированы по минимальному расстоянию до q.pq может содержать точки и записи структуры индекса.Вы начинаете с помещения корневой записи структуры индекса в pq.Затем вы начинаете извлекать элементы из pq.Когда вы сталкиваетесь с записью (узлом), вы разрешаете ее и возвращаете потомкам в pq.Когда вы сталкиваетесь с точкой, то вы находите своего следующего ближайшего соседа q.
В целом структура индекса имеет O (n) записей.Элемент из pq извлекается как O (log | pq |).Это делает время выполнения O (n * log | pq |).Вопрос в том, сколько элементов будет в среднем в pq.
У меня нет доказательств этого, но быстрый набросок, позвольте мне предположить, что среднее количество элементов в очереди должно быть около O (sqrt(n)) для L_1 и 2D-пространства.Обратите внимание, что размер очереди сильно зависит от метрики расстояния и размера ваших точек.
Собрав все это вместе, вы можете построить структуру индекса (O (n log n)), а затем для каждой точкиq ранжировать все остальные точки (O (n * log (sqrt (n)))) *
В целом это дает вам время выполнения O(n * log(n) + n^2 * log(sqrt(n))).
Однако, чтобы повторить @MBo: этоэто большая трудность для небольшого улучшения по сравнению с O (n ^ 2 * log (n))