If O(n^3) is permissible, then the following works: ---------------------------------------------------------------------- If we can find one point that falls on such a line, then it is easy to find the other points because the slope between this point and all other points that fall on this line will be the same.
So, the above problem can be solved if we find a point which has same slope to maximum number of other points. To do this, we can create a slope matrix such that matxi_slope[i][j] gives us the slope between point i and j. This can be done in O(n^2) Then for each row, we find maximum number of entries that are equal. This is O(n^3) The row with maximum number of equal slopes gives the points falling on the desired line. This can be converted to somewhat O(n^2) if hash-maps are used to find the maximum number of equal slopes in each row. -- 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.
