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