给定一组点，找出其中是否存在任意三个共线的点。

Question

在一组点中，如何找到任意三个共线的最佳算法？如果这不是微不足道的，请解释其复杂度。

谢谢
Bala

- Boolean

---

这个问题在课堂上进行了讨论，我知道O(N^2)算法。我找到了一个相当简单的O(N^2)算法来解决它。我想知道是否有更简单的算法。 - Boolean

是的，有二维点。 - Boolean

这个问题和另一个问题都是Algorist提出的Google面试题。 - FogleBird

@Algorist：不确定是否可以收到我的回答，因此使用评论进行ping。希望对您有所帮助。 - Aryabhatta

@Algorist - 你能与我们分享一个简单的O(N^2)算法吗？我还没有找到简单的算法... - Elazar Leibovich

@FogleBird 这也是《算法导论》一书中计算几何章节的一个（修改过的）问题。 - Dennis

Answer 1

如果你能想出比O(N^2)更好的算法，你可以发表它！

这个问题是3-SUM Hard，是否存在一个次二次算法（即比O(N^2)更好）仍然是一个未解决的问题。许多常见的计算几何问题（包括您的问题）已被证明是3SUM困难的，而这类问题正在增加。与NP-Hardness类似，3SUM-Hardness的概念在证明某些问题的“艰难程度”方面证明了其有用性。

要证明您的问题是3SUM困难的，请参阅此处的优秀调查论文：http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf 您的问题出现在上述论文的第3页（方便地称为3-POINTS-ON-LINE）中。

因此，目前已知的最佳算法是O(N^2)，而您已经拥有它 :-)

- Aryabhatta

---

@Moron - 有没有一种时间复杂度为O(n^2)的算法，不使用哈希表，就像@Strilanc描述的那样？ - Elazar Leibovich

@ Elazar：我相信这是可能的，通过考虑线映射到点，反之亦然（a，b）<-> y = ax + b的对偶。现在问题对应于找到度至少为6的对偶中的顶点。显然，这可以在O（n ^ 2）时间和O（n ^ 2）空间内实现。这本书：http://books.google.com/books?id=PBRJ-ruwOQcC 在第94页提到了它。 - Aryabhatta

这个答案现在有点过时了；在这个答案发布之后，出现了用于3SUM的次二次算法。不过，在实践中，简单的二次算法可能是最有用的。 - Daniel Lubarov

Answer 2

一个简单的O(d*N^2)时间和空间复杂度算法，其中d是维数，N是点的数量（可能不是最优解）：

• 在点集周围创建一个边界框（足够大，使得边界上没有点）
• 对于每一对点，计算通过它们的直线。
• 对于每条直线，计算它与边界框的两个碰撞点。
• 两个碰撞点定义了原始直线，因此如果有任何匹配的直线，它们也将产生相同的两个碰撞点。
• 使用哈希集合来确定是否有重复的碰撞点对。
• 只有当存在重复的碰撞点对时才存在3个共线的点。

- Craig Gidney

---

你的条件是必要的，但是否充分呢？在 (0,0)、(0,1)、(1,0) 和 (1,1) 处放置 4 个点以定义边界框。对 [(0.5,0.6),(0.5,0.7)] 的配对创建了一个与框相交的线段，它位于 (0.5,0)，与 [(0.4,0.1),(0.3,0.2)] 配对的线段也是如此。然而，这 8 个点中没有三个在任何公共直线上。 - Eric

这是一个充分条件，因为两个点可以定义一条直线。你只考虑了碰撞点对中的一个点；另一个点将不同，因此该对不匹配。 - Craig Gidney

没错。在第二步中，您可能需要提供更多详细信息，以澄清这两个碰撞点是如何组合成“碰撞点对”的。否则，读者可能会像我一样将第3步中的“一对碰撞点”与第2步中的“一对原始点”混淆。 - Eric

哦，我明白了，你把“pairs”解释成了两个相等的碰撞点，而不是两对相等的碰撞点。 - Craig Gidney

Answer 3

另一种简单的（甚至可以说是微不足道的）解决方案，它不使用哈希表，在O(n^2log n)时间内运行，并使用O(n)空间：

假设S是一个点集，我们将描述一种算法，该算法可以找出S是否包含某些共线的三个点。

对于S中的每个点o： 1. 通过o的平行于x轴的一条直线L。 2. 用其反射替换在L以下的S中的每个点。（例如，如果L是x轴，则对于x>0的点(a,-x)，在反射后将变成(a,x)）。让新的点集为S'。 3. S'中每个点p的角度是其到L的垂线与线段po的夹角。让我们按照它们的角度对点S'进行排序。 4. 遍历排序后的点S'。如果有两个连续的点与o共线，则返回true。

如果循环中未发现共线点，则返回false。

循环运行n次，每次迭代执行nlog n步骤。很容易证明，如果有三个点在同一条直线上，它们将被找到，否则我们将什么都找不到。

- Elazar Leibovich

---

你只需要对一半的点进行外循环：那些具有最大 y 坐标值的点，对吗？另外，当你说“有两个共线的连续点”时，你实际上是指“有两个连续的共线点与点 o 共线”，我的理解正确吗？ - Qiang Li

第一个观察是正确的，尽管它不会改变复杂度。对于另一半点来说，由于对称性，这样做是等效的。请注意，您必须首先对它们进行排序，这使算法变得有点更加复杂。第二个观点也是正确的，已经修正了，谢谢。 - Elazar Leibovich