检测二维空间中两点距离最远的两个点的最快方法是什么？

Question

我需要得到两个距离最大的点。

最简单的方法是计算它们之间的距离，但该解决方案将具有二次方复杂性。

所以我正在寻找任何更快的解决方案。

Answer 1

如何：

1确定点集的凸包。
2找到船体上各点之间的最长距离。

这应该允许您在检查距离时忽略所有不在船体上的点。

Answer 2

为了详细说明rossom的回答是：

1. 查找其可以在O发现（N log n）的点时间，像格雷厄姆的扫描或O的一种算法的凸包（N日志1H）时间我假设的其他算法很难实现
2. 从一个点开始，比如说A，并且循环通过其他点找到距离它最远的那个点，如B所示。
3. 将A推进到下一个点并将B推进到它离A再远一点。如果这个距离大于第二部分的距离，则将其存储为最大。重复，直到你已经循环遍历集合中的所有点A

第2和第3部分采用分摊的O（n）时间，因此整个算法的时间取决于O（n log n）或O（n log h）多少时间你可以花费在实现凸包上。 O（n^2）应该可以正常工作（除非你多次执行）。这很好，但是如果你只有几千分（如你所说），O（n^2）应该可以正常工作。