找到相距最远的点的算法——比 O(n^2) 更好? [英] Algorithm to find points that are furthest apart -- better than O(n^2)?

问题描述

在我的程序中，我有一组点.出于重新缩放的目的，我正在搜索相距最远的两个节点，然后计算一个因子，将所有坐标乘以该因子，以使最大距离等于我定义的某个预定义的距离.

In my program, I have a set of points. For purposes of rescaling, I am searching for the two nodes that are furthest apart, and then computing a factor by which to multiply all coordinates so that the maximum distance is equal to some predefined one I define.

然而，我用来找到相距最远的两个点的算法对于大量点集是有问题的，因为它是 O(n^2);伪代码(已计算的距离被跳过):

The algorithm I am using to find the two points furthest apart is, however, problematic for large sets of points, as it is O(n^2); pseudocode (distances that were already calculated are skipped):

 for each point in points:
     for each other point in points:
         if distance between point and other point > max
             max = distance between point and other point

有更快的方法吗?

推荐答案

如果您只需要比例而不是确切的点，您可以在 O(n) 时间内完成此操作，但有一定的误差.想想制作边界框的简单案例.从所有点计算最小 x 值，最大 x，最小 y 和最大 y.这四个数字为您提供了围绕点的最大边界框，最大误差为 1 - (1/sqrt(2)) 约 30%.您可以通过在正方形中添加更多边来减少这种情况.想想八边形的情况.要计算其他边的最小值和最大值，您必须旋转坐标系.

If you just need the scale and not the exact points you can do this in O(n) time with some error margin. Think about the simple case of making a bounding box. Calculate the minimum x value from all the points, the maximum x, the minimum y and the maximum y. These four numbers give you a maximum bounding box around your points with max error of 1 - (1/sqrt(2)) about 30%. You can reduce this by adding more sides to your square. Think about the case of an octagon. To calculate the min and max values for the other sides you have to rotate your coordinate system.

错误与运行时间像这样分解.

Error vs run time breaks down like this.

形状 - 运行时间 - 最大误差

shape - run time - max error

• 正方形 - 2N - 30%
• 八角形 - 4N - 16%
• 16 面 - 8N - 4%
• 32 面 - 16N - 1%

这是我想出的最大误差公式.

Here's the equation for the max error I came up with.

angle = 180 / sides
max_error = (1 / cos angle) - cos angle

让我知道我是否应该添加一个图表来解释这一点.

Let me know if I should add a diagram explaining this.

这篇关于找到相距最远的点的算法——比 O(n^2) 更好?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！