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

Question

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

（还有该方法的实现方式如何？

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

Answer 1

你需要一个像 k-d 树这样的"空间分区"数据结构。