在给定m个点的四维空间中,如何有效地找到两个最远的点(欧氏距离)?

问题的计算随着维数的增加而增大。大约4岁的时候,你最好用暴力。

如果这个数据有一些已知的功能,你可以减少一些东西。如果你经常这样做,但分数变化不大。您可以通过在每次添加新点时检查每个点的最远点来构建分组,该点缓存来自蛮力的数据。插入时得到O(N),最远查询时得到O(N)。但是,你需要这样做N次,给你O(N^2)。

如果同时对数据进行集群化,则可以稍微减少这一点。所以你在插入过程中定义了一组点,你可以确定,因为你的房子在纽约,巴黎的房子不能比澳大利亚的房子更远。你可以这样做,因为你有集群中的数据。但是,这不会给你省那么多钱,因为在4D中,事情很难优化,因为你最终需要更多的盒子来存储4D中的簇,而大多数有趣的优化就是一个证明,既然你已经在4D中超过了这个距离,你可以排除所有其他点。这是伟大的二维,但这些技巧变得越来越混乱与新的维度。

请看这个问题的答案: How to find two most distant points? 要找到凸面外壳,可以使用以下方法: https://en.wikipedia.org/wiki/Gift_wrapping_algorithm