for every point Pi, we compute the angle of the line which connects Pi and other point Pj, and sort all Pj-s by the angle and then let j from i to n and j!=i, finding the max collinear point set that includes Pi. the complexity of this process is O(n*ln(n)+n).Let i=1 to n ,so the complexity of the whole problem is O(n^2*ln(n)) .
On 5月14日, 下午10时06分, Balachander <[EMAIL PROTECTED]> wrote: > Hey.. > > How can reduce the Comp from O(n) to O(log n) > How are arranging the lines [ nC2 lines] > for the purpose of finding the max no of collinear points > > For finding all lines O(n^2) > For Checking the presence ..O(n) > > Pls reply ,,How can u reduce the comp to Log n. > > Bala > > On May 14, 6:57 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote: > > > > > I have a brute force solution with the time complexity of > > O(n^2ln(n))... > > how can we impove it? > > On 5月14日, 下午6时50分, PopUp <[EMAIL PROTECTED]> wrote: > > > > I have brute force solution, this was asked in Google Interview. > > > > On May 14, 1:36 pm, "Cool Guy" <[EMAIL PROTECTED]> wrote: > > > > > I think that this problem is similar to cryptology. > > > > (Cryptology is method for one solution when exists a lot of numbers, but > > > > reverly think, I think that max collinear points will be find) > > > > > Actually, I don't have any idea. :) > > > > > Can you any idea for resolving this problem? > > > > > 2007/5/14, PopUp <[EMAIL PROTECTED]>: > > > > > > HI, > > > > > Great group!! > > > > > I have a problem, some of you might have heard about that. We have set > > > > > of n points in space. Now we have to find a set(with the max elements) > > > > > of collinear points or we can say find the max collinear points. > > > > > > Thanks, > > > > > Popup- 隐藏被引用文字 - > > > > - 显示引用的文字 -- 隐藏被引用文字 - > > - 显示引用的文字 - --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
