给定m个四维点，如何高效地找出具有最大欧几里得距离的两个点？
目前，我只是使用蛮力方法，通过两个嵌套的for循环检查每对距离（O(m ^ 2)），但这非常糟糕，因为它无法扩展。
如何高效地找到给定m个点的4维空间中距离最远的两个点（欧几里得距离）？
5
- user3243499
10
可能是[查找距离最远的点的算法--比O(n^2)更好的算法？]（https://dev59.com/HWw15IYBdhLWcg3wkcuq）的重复。 - MSalters
顺便说一下，在这里讨论了在不同维度中使用三角不等式来减少距离检查数量的效率：https://stackoverflow.com/questions/35923497/biggest-diameter-of-a-set-with-a-distance-function/35930703#35930703 - m69 ''snarky and unwelcoming''
1@m69 你确定在四维空间中三角不等式成立吗？什么是四维三角形？ - גלעד ברקן
@גלעדברקן 高维三角不等式: https://people.math.gatech.edu/~cain/notes/cal5.pdf - m69 ''snarky and unwelcoming''
1@m69 它说这个不等式在更高的维度中成立！ - גלעד ברקן
显示剩余5条评论
2个回答
0
问题的计算随着维度的增加而增加。在大约4个维度时，你通常最好使用暴力方法。
如果有一些已知的功能可以减少工作量。比如，如果你经常这样做，但点的变化不大。你可以通过每次添加一个新点时检查每个点的最远点来构建分组，并缓存来自暴力方法的数据。插入的时间复杂度为O(N)，最远点查询的时间复杂度也为O(N)。但是，你需要这样做N次，从而得到O(N^2)。
如果你还将数据聚类，就可以将其减少一些。因此，在插入期间定义一组点，你可以确定由于你的房子在纽约，所以巴黎没有房子更远，因为你已经将其与澳大利亚的房子进行了比较。你之所以能够这样做，是因为你有聚类数据。但是，这并不能节省太多时间，因为在4D中，优化变得非常困难，因为你需要更多的盒子来存储聚类，而大部分有趣的优化都是证明，由于你已经超过了4D中的那个距离，所以你可以排除所有其他点。在2D中这很棒，但是这些技巧随着新维度的增加变得越来越混乱。
- Tatarize
-1
请查看这个问题的答案：如何找到两个最远的点？
要找到凸包，您可以使用这个：https://en.wikipedia.org/wiki/Gift_wrapping_algorithm
- Peter Chikov
7
这些链接与二维相关，与此无关。不幸的是，在 4 维中找到极值需要 O(n²) 的时间复杂度。 - user1196549
这个算法可以推广到第三维及更高维度。要查看算法在第三维中的可视化，请参见此处：https://dccg.upc.edu/people/vera/wp-content/uploads/2014/11/GA2014-ConvexHulls3D-Roger-Hernando.pdf - Peter Chikov
如果它不能降低复杂度，那有什么用呢？ - user1196549
暴力算法在每种情况下都需要n^2的时间。礼品包装算法需要nF的时间，其中F是凸包面的数量。最坏情况下，如果所有点都在凸包面上，则确实需要n^2的时间。但在平均情况下，运行时间较短。 - Peter Chikov
1@PeterChikov 三角不等式也可以改善平均情况，但不能改善最坏情况。聚类也可能会有所帮助。 - m69 ''snarky and unwelcoming''
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接