给出 2d 点的列表和最大距离 d，有什么比 O(n^2) 更好的方法来查找每个点位于 d 范围内的点。我不需要解决方案，只需要一些起始想法。
最佳答案
使用kd树等空间索引结构，可以获得O(n log n)
编辑
啊，我想我误解了你的评论。如果您在查询中设置 n 个最近邻，在最坏的情况下，单个搜索成本为 O (n log n)，但您可以在每个找到的最近点上放置一个标志，以指示它们是否已经属于特定簇。然后您不必再次对这些点执行最近邻查询。所以最终的复杂度仍然是O(n log n)。以下是有关此类范围搜索的更多详细信息 http://www.cs.utah.edu/~lifeifei/cs6931/kdtree.pdf .
我在这里假设期望的行为是从考虑中删除一个点(如果它已经属于一个集群)。也许您可以澄清一下问题说明？
关于algorithm - 给定一个点列表，如何确定哪些点彼此之间的距离在一定范围内，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24481809/