Hi guys. I still think you can do it in O(n^2) if you grant that a hash table is O(1). For each pair of points (there are n(n-1)/2 of them, which is O(n^2), find A, B and C such that , Ax + By + C = 0
and furthermore ensure that A^2 + B^2 = 1. (Alternately if you are using rational arithmetic, you can express A, B, and C as integers with gcd of 1.) Finally, if you have A<0, then invert the signs of A,B,C so that A is positive. If A is 0 and B<0, then invert the signs so that B is positive. This computation is robust and produces a unique (A,B,C) triple for every infinite line. Now use the (A,B,C) triples of the pairs as hash keys. The hash values are sets of points. Pick your favorite set data structure with O(1) time to add an element. After inserting all the O(n^2) pairs into the table, just read all the sets looking for those with 3 or more elements (or the maximum size sets for the earlier problem). On Oct 24, 10:03 am, ravindra patel <[email protected]> wrote: > @Dave > I was wrong. It can't be done in O(n^2) time. The best we can do is sort > each row like you suggested in your other post. That will still be > O((n^2)logn). > > Thanks, > - Ravindra > > > > On Sun, Oct 24, 2010 at 7:06 PM, Meng Yan <[email protected]> wrote: > > for the 3th step, > > for i=1 to n > > for j=i+1 to n > > for k=j+1 to n > > compare A[i,j] and A[j,k] > > if A[i,j]==A[j,k] > > find i,j,k are collinear. > > > so we should need O(n^3), is it right? > > > On Sun, Oct 24, 2010 at 1:05 AM, ravindra patel > > <[email protected]>wrote: > > >> Can be done in O(n^2) time using the slope as people suggested above. > > >> 1- Sort the points in increasing order of x cord. O(nlogn) > >> 2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) ) - > >> O(n^2) [Note that point i and j are sorted in increasing order of x] > >> 3- find a pair of A[i,j] and A[j,k] with same slope. [Can be done in > >> O(n^2)] > > >> Thanks, > >> - Ravindra > > >> On Sun, Oct 24, 2010 at 10:11 AM, Dave <[email protected]> wrote: > > >>> @Preetika: Then you have to look for duplicates in an array of n(n-1)/ > >>> 2 real numbers. I think this takes the complexity above O(n^2). > > >>> Dave > > >>> On Oct 23, 10:54 pm, preetika tyagi <[email protected]> wrote: > >>> > You have to scan every pair of points only once to get the value of 'm' > >>> and > >>> > 'a', so the time complexity would be O(n^2). > > >>> > On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan <[email protected]> > >>> wrote: > >>> > > there are (n*(n-1))/2pairs of points. I think if we use your method, > >>> the > >>> > > time complexity should be O(n^4). > > >>> > > Is it possible to put all points into k different domain and using > >>> > > T(n)=T(n/k)+f(n) to solve this problem? > > >>> > > On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi < > >>> [email protected]>wrote: > > >>> > >> Is there any specific need to use recursion? > > >>> > >> One alternate is to find slope and constant (m and c) for every pair > >>> of > >>> > >> points and same value of m & c will specify the points on the same > >>> line. > >>> > >> Time complexity is O(n*n). > > >>> > >> On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan <[email protected] > >>> >wrote: > > >>> > >>> Given n point on the plane, find out whether any 3point on the same > >>> > >>> line. > > >>> > >>> How to use recursion to solve the problem? Could you help me find > >>> the > >>> > >>> algorithm and give the time complexity? > > >>> > >>> Bests, > >>> > >>> Claire > > >>> > >>> -- > >>> > >>> 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]<algogeeks%2bunsubscr...@googlegroups.com> > >>> <algogeeks%2bunsubscr...@googlegroups.com> > >>> > >>> . > >>> > >>> For more options, visit this group at > >>> > >>>http://groups.google.com/group/algogeeks?hl=en. > > >>> > >> -- > >>> > >> 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]<algogeeks%2bunsubscr...@googlegroups.com> > >>> <algogeeks%2bunsubscr...@googlegroups.com> > >>> > >> . > >>> > >> For more options, visit this group at > >>> > >>http://groups.google.com/group/algogeeks?hl=en. > > >>> > > -- > >>> > > 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]<algogeeks%2bunsubscr...@googlegroups.com> > >>> <algogeeks%2bunsubscr...@googlegroups.com> > >>> > > . > >>> > > For more options, visit this group at > >>> > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > >>> > - Show quoted text - > > >>> -- > >>> 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]<algogeeks%2bunsubscr...@googlegroups.com> > >>> . > >>> For more options, visit this group at > >>>http://groups.google.com/group/algogeeks?hl=en. > > >> -- > >> 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]<algogeeks%2bunsubscr...@googlegroups.com> > >> . > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > 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]<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- 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.
