Можно ли найти ближайшую точку ко всем точкам субквадратического времени?

Question

Алгоритмический вопрос.

Вход:

• Список точек данных X
• Метрика функция для точек dist(x,y) данных, занимает O (1) время, чтобы оценить и удовлетворяет неравенству треугольника

Есть алгоритм, который может возвращать вектор точек данных Y такой, что Y[i] является ближайшей точкой в ​​X до X[i] в субквадратичное время?

Очевидно, это возможно в O (n^2), потому что вы можете просто проверить каждую точку. Мне интересно, можно ли использовать неравенство треугольника, чтобы улучшить это. Меня также интересовали бы приближенные алгоритмы с доказуемыми границами (т. Е. Что-то вроде Y[i] не более (1 + log (n)), умноженное на расстояние от X[i] как минимум).

Answer 1

Нет такого алгоритма. Рассмотрим метрику, где все, кроме одной пары точек, находятся на расстоянии 1. Эта пара не может быть найдена без консультации с ее конкретной записью оракула расстояния, которая требует запросов Omega (n^2) в худшем случае.

Cover trees можно использовать для решения проблемы с точными соседями. Временная граница зависит от так называемого показателя удвоения метрики.