给定一组点,我如何找到彼此最远的两个点？

Question

可能重复:
最大线性尺寸2d点集

我可以计算每个点之间的距离并取最大值,但是当有大量(> 1000)点数时,这听起来不是一种非常有效的方法.

注意:这适用于iPhone,因此我没有大量的处理能力.

Answer 1

为什么不计算点的凸包呢？根据您使用的算法,它需要一个O(n)或一个O(n log n)时间,并消除考虑的所有内部点.然后,只检查这些最外面的点,找到距离最远的两个点.

Answer 2

你要求计算集合的直径.标准技术是首先计算凸包,这减少了找到凸多边形直径的问题.即使在您没有消除任何积分的情况下,这些添加的信息正是有效解决问题所需要的.然而,找到凸多边形的直径并非完全无关紧要; 一些已发表的论文与这项任务的算法结果是不正确的.

这是对任务的正确O(n)算法的一个相当可读的讨论(其中n是凸包中的点数).

另外,请注意iphone不是那么有限; 即使是完全天真的算法,精心编写的实现也可以在不到十分之一秒的时间内处理1000个点.当然,使用正确的算法会让你走得更快=)