Given N points how to find the maximum number of points which are on a circle?

Yesterday, an interesting question comes to mind, Given N points, how do you find the m开发者_如何学运维aximum number of points that are on a circle?

Can you suggest anything other than brute-force? What is O(?)?

It seems that there is O(N^3*log N) algorithm :)

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)

Actually given two points and radius two circles are generally possible, but taking this into account (splitting each group into to) will not change algorithm complexity.

Except for degenerate cases, any three points on a plane are on a circle. So an obvious O(n⁴) algorithm is to enumerate all sets of three points that are not on a line (O(n³)), calculate the center of the circle (maybe there can be two, I'm not sure) going through the three points, and then iterate through the other points and check which ones are on the same circle, count, and after algorithm has finished, report the maximum.