performance - 查找与给定坐标最近的点 - 数据结构

Question

什么是保存二维点集合的好数据结构，以便以后我可以有效地调用像 collection.pointsCloserThanDistance(float d, float[] coordinates) 这样的方法？- 此方法将返回一个列表，其中每个点到给定坐标的距离小于或等于 d。

（以及该方法的实现方式如何？）

最简单且可能不太好的解决方案是标准数组，然后将每个点与给定坐标进行比较。这是 O(n)，n = 点数。但是可能有 O(m), m = 到给定坐标的距离小于或等于给定值的点数。

Answer 1

您需要像kd 树这样的“空间分区”数据结构。