2D,C中的所有k个最近邻居

>在点之上创建一个更大的网格.
>线性地遍历这些点,并为每一个点找出它所属的大“单元”(并将点添加到与该单元格相关联的列表中).

(这可以在每个点的恒定时间内完成,只需对点的坐标进行整数除法.)
>现在再次线性地浏览这些点.要找到10个最近的邻居,您只需要查看相邻较大的单元格中的点.

由于您的点数相当均匀,您可以按照与每个(大)单元格中的点数成比例的时间进行此操作.

这是描述情况的(丑陋)图片：

单元格必须足够大(中心),相邻单元格必须包含最接近的10个点,但要小到足以加速计算.您可以将其视为“哈希函数”,您可以在其中找到同一存储桶中的最近点.

(注意严格来说,它不是O(n),但通过调整较大单元格的大小,你应该足够接近.:-)