我有一组二维点/坐标，我需要在所有点对之间遵守一定的最小距离。此外，每个点都与一些我想维护的信息相关联，可能将该信息与其他点中包含的其他信息合并。
问题是我必须创建一个新集合，其中所有点对之间的最小距离都得到尊重，并且丢失的信息最少。
我想不出一种算法或方法可以在任何时间成本下解决这个问题。
如有任何帮助，我们将不胜感激。
最佳答案
朴素的解决方案——速度不快 (O(n³)) 但可能会让您入门:
- 找到任意两点之间的最小距离，即全局具有最小距离 (O(n²)) 的点对
- 如果距离大于所需的最小距离，则完成
- 合并两点并从 1 开始。
这会使用蛮力算法将最接近的点一一合并，直到达到最小距离。
P.S.:正如@Yyes Dauous 在评论中提到的那样，关闭对可以在 O(n log n) 中找到，如所描述的那样。在相应的维基百科文章中(其中包括一些在这里可能有用的动态方面的讨论):https://en.wikipedia.org/wiki/Closest_pair_of_points_problem
关于合成一组二维点的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32682604/