给定一组点,找出三个点中的任何一个是否共线

Question

如果任何三个点在一组点中共线,那么找出最佳算法是什么？如果不是微不足道,请解释复杂性.

由于
巴拉

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点在线).

所以,目前最着名的算法是O(N ^ 2),你已经拥有它了:-)

Answer 2

一个简单的O(d*N ^ 2)时间和空间算法,其中d是维数,N是点数(可能不是最优):

• 在点集周围创建一个边界框(使其足够大,以便边界上没有点)
• 对于每对点,计算通过它们的线.
• 对于每条线,使用边界框计算其两个碰撞点.
• 两个碰撞点定义原始线,因此如果有任何匹配线,它们也将产生相同的两个碰撞点.
• 使用哈希集来确定是否存在任何重复的冲突点对.
• 当且仅当存在重复时,有3个共线点.