给定N点如何找到圆上的最大点数？

Question

昨天,一个有趣的问题浮现在脑海中, Given N points, how do you find the maximum number of points that are on a circle?

除了蛮力外,你能提出什么建议吗？什么是O(？)？

Answer 1

似乎有O(N ^ 3*log N)算法:)

iterate through all pairs of points - O(N^2)
    for each point of the rest compute radius of circle including that point and the selected pair of points - O(N)
    sort points by this radius - O(N*log N)
    select from the resulting array the biggest group with same radius - O(N)

实际上给定两个点和半径通常是两个圆,但考虑到这一点(将每个组拆分成)将不会改变算法的复杂性.

Answer 2

除了退化情况,平面上的任何三个点都在圆上.所以一个明显的O(n ⁴)算法是枚举所有不在一条线上的三个点(O(n ³)),计算圆的中心(可能有两个,我不确定)通过这三个点,然后遍历其他点并检查哪些点在同一个圆上,计数,并在算法完成后,报告最大值.