这里似乎有一个类似的问题，但我对答案的清晰性和实用性都不满意。在最近的一次采访中，有人问我将存储我的大量浮点数的数据结构，以便我为自己或最近的邻居查找新来的。我说我会使用二叉搜索树，并尝试使其平衡以实现 O(log n)。
然后问题扩展到两个维度：我将使用什么数据结构来存储大量 (x,y) 对，例如地理坐标以便快速查找？我想不出一个令人满意的答案，当扩展到 K 维时完全放弃了。直接使用使用坐标值来“分割”空间的 k 维树似乎不起作用，因为靠近原点但在不同象限内的两个接近点可能最终落在很远的叶子上。
采访结束后，我想起了很好地划分 K 维空间的 Voronoi 图。使用什么数据结构实现这一点的最佳方法是什么？如何进行查找？我觉得这个问题在计算机科学中是如此普遍，以至于现在它甚至有一个专门的数据结构。