algorithm - AO(n*log(n)) 算法找到具有最低斜率的段（在 n*n 段中）

Question

给定定义n ²条线的不同点的P={p ₁ ,...,p _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).

Answer 2

根据点的 y 位置对点进行排序（使用任意数量的众所周知的算法 n log n 次）。按从 0 到 n - 1 的顺序浏览列表，将每个点对的斜率与迄今为止发现的最低斜率进行比较。（那是 n 次）。

总的来说，这将是 O(n log n)。

在伪代码中：

Let P be the list of points (this list starts at 1)
n = P.length
S = quicksort("a.y < b.y", P) // or some other O(n log n) algorithm
bestSlope = float.inf
let p1 and p2 be points
for i = 1 to n-1:
    currSlope = abs((P[i].y - P[i+1].y) / (P[i].x - P[i+1].x))
    if currSlope < bestSlope:
        bestSlope = currSlope
        p1 = P[i]
        p2 = P[i+1]