CODEWITHSUNDEEP
algorithmmathgraph
user467871
user467871

Reputation:

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 maximum number of points that are on a circle?

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

Upvotes: 16

Views: 3256

Answers (2)

maxim1000
maxim1000

Reputation: 6365

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.

Upvotes: 16

Antti Huima
Antti Huima

Reputation: 25512

Except for degenerate cases, any three points on a plane are on a circle. So an obvious O(n4) algorithm is to enumerate all sets of three points that are not on a line (O(n3)), 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.

Upvotes: 7

Related Questions