algorithm - 存储实时图形点的最佳方式

Question

我最近在一次编程面试中被问到以下问题：

“给定笛卡尔图的连续图形点 (X, Y) 流，设计一个数据结构来存储它们，以便在任何时候以最有效的方式搜索与给定点距离为 k 的所有相邻点时间复杂度方面。”

我的想法是使用关联列表。列表的每个节点都会有 X 点作为键，其对应的 Y 点作为值。请建议任何更好的数据结构。

谢谢

Answer 1

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

另见 K-DTree、四叉树等。

例如，在 kd 树中找到 k 个最近的邻居将花费 O(k log n) 或 O(log n) 用于常数 k，时间。

将点存储在 X -> Y 映射中对您没有帮助，因为如果 Y 坐标非常接近，沿 X 维度彼此远离的点仍然可以是最近的邻居。