algorithm - 一种 O(n*log(n)) 算法，用于查找具有最低斜率的段(在 n*n 段中)

Question

给定 P={p₁,...,p_n} 不同的点定义 n ² 行，编写一个算法，在最坏情况下以 O(n*log(n)) 时间复杂度找到具有最低斜率(最小绝对值)的线案例。

Answer 1

定理:

• 给定一组点 P。
• 选择 P 中的 A 和 C 两点，使线 AC 具有最小的绝对斜率(如问题中所定义)。
• 对于多对点具有相同斜率的退化情况，令 AC 为具有该斜率的最短线段。
• 那么在 P 中不存在 Y 坐标在 A 和 C 之间的其他点。

证明(反证法):

• 假设至少有一个点 B，其 Y 坐标在 A 和 C 之间。
• 那么存在三种可能的情况:
  • B 与 A 和 C 共线。那么直线 AB 或 BC 的斜率与 AC 相同，但两条都比 AC 短。矛盾。
  • B 落在 AC“上方”的半平面内。然后直线 AB 的斜率比 AC 的斜率小。矛盾。
  • B 落在 AC“下方”的半平面中。那么线 BC 的斜率比 AC 的斜率小。矛盾。
• 所有情况都导致矛盾，因此 A 和 C 之间没有点。
• QED。

通过这个定理，您可以清楚地使用@Zshazz 的算法找到正确的对——因为它们将是最近的邻居——在 O(n*log n) 中。