数百万个3D点：如何找到最接近给定点的10个点？

Question

3-d中的一个点由（x，y，z）定义。任何两个点（X，Y，Z）和（x，y，z）之间的距离d为d = Sqrt [（Xx）^ 2 +（Yy）^ 2 +（Zz）^ 2]。现在，文件中有一百万个条目，每个条目都是某个空间点，没有特定的顺序。给定任意点（a，b，c），请找到与其最近的10个点。您将如何存储百万点，以及如何从该数据结构中检索这10点。

Answer 1

如果一百万个条目已经在文件中，则无需将它们全部加载到内存中的数据结构中。只需保留到目前为止找到的前十个点的数组，然后扫描一百万个点，即可随时更新前十个列表。

这是点数的O（n）。