Лучший способ хранения в реальном времени точек графика

Question

Я недавно был задан следующий вопрос в интервью кодирования:

«Учитывая непрерывный поток точек графа (X, Y) декартова графика, дизайн структуры данных для хранить их так, чтобы поиск всех соседних точек на расстоянии k от данной точки в любое время должен выполняться наиболее эффективным способом с точки зрения временной сложности ».

Моя идея - использовать ассоциативный список. Каждый узел списка будет иметь X-точку в качестве ключа, а его соответствующая точка Y - как значение. Пожалуйста, предложите любую лучшую структуру данных.

Благодаря

Answer 1

http://en.wikipedia.org/wiki/R_tree

Смотрите также K-DTree, Quad дерева и т.д.

Например, найти K ближайших соседей в кД дерева будет принимать O (к лог-н), или O (log n) для константы k, времени.

Сохранение точек в X -> Y-сопоставлении не поможет вам, так как точки, находящиеся далеко друг от друга по размеру X, все еще могут быть ближайшими соседями, если их координаты Y очень близки.