algorithm - CLRS :33. 1-4 :Show how to determine in O(n*n*lg n) time whether any three points in a set of n points are colinear?

Question

我正在阅读 CLRS 的计算几何算法书。在练习 33.1-4 中，它要求我们“显示如何在 O(n*n*lg n) 时间内确定一组 n 点中的任意三个点是否共线？”通过一次取三个点并进行叉积，可以在 O(n*n*n) 时间复杂度内轻松完成此操作，但我无法理解如何在 中完成此操作>O(n*n*lg n) 时间。需要帮助。

Answer 1

令 slope(P, Q)，对于任意两点 P 和 Q，是通过 的直线的斜率>P 和 Q。现在，三个点，比如 P、Q 和 R，共线当且仅当 slope(P,Q) = slope(P, R)。因此，固定 P，您可以在 O(n*log n) 时间内确定是否还有另外两个点 Q 和 R 这样 PQR 就是一行。这很容易通过为 n 点集中的所有其他点 Q 计算 slope(P,Q) 并检查是否有任何重复 - 使用类似集合的结构或只是排序并检查重复项。现在，遍历 P 的所有选择，为您提供 O(n*n*log n) 的运行时间。