时间戳

首页 > 解决方案 > 获取 2D 平面中最远的 2 个点的算法（用于家庭作业）

algorithm - 获取 2D 平面中最远的 2 个点的算法（用于家庭作业）

问题描述

我必须制定一个有效的算法来获得彼此最远的两个点，并且我试图获得 O(nlogn) 复杂度。我搜索了一种有效的算法，但我能找到的只是最近的点。

输出应该只打印 2 个点。

我现在发现的是来自 GeeksForGeeks 的算法：https ://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/ 但适用于最近的点。

而这个解决方案：

mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/

对于家庭作业来说，这看起来很复杂。

第一种方法，看起来很奇怪，而且我认为它不适用于我的问题。

任何帮助，将不胜感激。

标签： algorithmperformancepoints

解决方案

好吧，这是作业，所以没有代码示例:)

这是 O(n log n) 方法：

  1. 使用任何 O(n log n) 凸包算法找到所有给定点的凸包

  2. 现在我们可以注意到最远的 2 个点仍然在凸包上

  3. 我们可以 在 O(n) 时间内使用旋转卡尺技术找到这些点

推荐阅读