There are only O(n^2) pairs of points. So compute the normalized coefficients (A,B,C) of the line passing through each pair: Ax + By + C = 0 where sqrt(A^2 + B^2) = 1 and either A>0 or (A=0 and B = 1). This is simple algebra. Now you can hash all the points in the pairs using their (A,B,C) triples as keys. This will give you equivalence classes of points. The largest equivalence class is your answer, and you'll have it in O(n^2) time.
The interesting thing is to consider whether it can be done in less than O(n^2)... On Oct 13, 5:52 am, Mridul Malpani <[email protected]> wrote: > There are n points in 2d space.we have their (x,y) co-ordinates. you > have to find the maximum set of points that are colinear? > I have used brute force, time =O(n^4). he wants a solution in O(n^3 or > n^2). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
