Roh*_*nga 5 algorithm geometry data-structures
N 点数作为输入.
让我们说吧(x1,y1), (x2,y2)... (xn,yn).
是否有非组合解决方案来找到最大共线点数？它们可以安排在一个有助于这种计算的奇特数据结构中吗？
Joh*_*ski 10
对于每个点i,找到每个其他点j的斜率并查找重复点.通过对斜率进行排序并比较相邻值可以找到重复项.点i与每组重复点中的点共线.随时跟踪最大集合.
对于每个i,您有n-1个斜率来计算,排序和比较.因此,使用(n log n)排序,算法的复杂度为O(n ^ 2 log n).