Является ли дерево KD одним из лучших алгоритмов для движущихся объектов?

Question

Скажем, у вас есть список объектов, и каждый объект должен рассчитать свой ближайший объект для съемки. Этот объект имеет топор и значение y. Также объекты движутся. Будет ли дерево KD по-прежнему полезным? Я не уверен, потому что если объекты движутся, вы должны продолжать создавать это дерево kd.

Какой алгоритм я могу использовать для лучшей скорости (предпочтительно с Big O)

Answer 1

Дерево kd - это очень, очень эффективная структура данных для определения ближайших соседей в евклидовом пространстве с координатами.
Для создания проблем с генерацией дерева kd потребуется действительно огромное количество объектов (оно генерируется в O(n log²n), так что почти линейное время, и поиск всех ближайших соседей занимает O(n log n), тоже очень дешево). Таким образом, у вас, вероятно, будут проблемы с остальной частью программы.

Судя по вашему вопросу, кажется, что все, что вам нужно отслеживать, - это ближайший сосед ряда точек в евклидовом пространстве. Я бы посоветовал вам начать с ванильной реализации дерева kd, а в extreme и маловероятно , когда генерация дерева kd будет слишком дорогой с точки зрения время или память, чтобы попытаться найти способ отслеживать несколько соседей для каждого элемента и обновлять список только при необходимости.
Но, честно говоря, я работал с деревом kd в прошлом, и я помните, что несмотря на то, что набор данных довольно большой (десятки миллионов точек в 2D-пространстве), генерация и поиск были достаточно быстрыми, чтобы казаться незначительными по сравнению с другими операциями.