Кажется, здесь есть похожий вопрос , но я не был удовлетворен ни ясность ответа, ни его практичность. В недавнем интервью меня спросили, в какой структуре данных я буду хранить свой большой набор чисел с плавающей запятой, чтобы искать новое поступление для себя или своего ближайшего соседа. Я сказал, что буду использовать бинарное дерево поиска и попытаюсь сделать его сбалансированным для достижения O(log n).
Затем вопрос был расширен до двух измерений: какую структуру данных я буду использовать для хранения большого набора пар (x, y), таких как географические координаты, для быстрого поиска? Я не мог придумать удовлетворительного ответа и полностью сдался, когда его расширили до K-измерений. Непосредственное использование k-мерного дерева, которое использует значения координат для «разделения» пространства, похоже, не работает, поскольку две близкие точки вблизи начала координат, но внутри разных квадрантов могут оказаться на очень далеких листьях.
После интервью я вспомнил о диаграммах Вороного для красивого разбиения K-мерного пространства. Каков наилучший способ реализации этого с использованием какой структуры данных? Как будут выполняться поиски? Я чувствую, что этот вопрос настолько распространен в компьютерных науках, что к настоящему времени у него даже есть специальная структура данных.
