@Gene: The problem is that the quantities A, B, and C are likely to be floating point numbers because the x and y coordinates of the points are floating point numbers. You probably are going to want to compare for equality to within a tolerance. You can do that if you sort the slopes, but how do you do it with a hash table?
Dave On Oct 25, 9:11 pm, Gene <gene.ress...@gmail.com> wrote: > 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 <ravindra.it...@gmail.com> 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 <mengyan.fu...@gmail.com> 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 > > > <ravindra.it...@gmail.com>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 <dave_and_da...@juno.com> 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 <preetikaty...@gmail.com> 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 <mengyan.fu...@gmail.com> > > >>> 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 < > > >>> preetikaty...@gmail.com>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 <mengyan.fu...@gmail.com > > >>> >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 algoge...@googlegroups.com. > > >>> > >>> To unsubscribe from this group, send email to > > >>> > >>> algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. > > >>> > >> To unsubscribe from this group, send email to > > >>> > >> algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com. > > >>> > > To unsubscribe from this group, send email to > > >>> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > >>> <algogeeks%2bunsubscr...@googlegroups.com> > > >>> > > . > > >>> > > For more options, visit this group at > > >>> > >http://groups.google.com/group/algogeeks?hl=en.-Hidequoted 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 algoge...@googlegroups.com. > > >>> To unsubscribe from this group, send email to > > >>> algogeeks+unsubscr...@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 algoge...@googlegroups.com. > > >> To unsubscribe from this group, send email to > > >> algogeeks+unsubscr...@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 algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@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 -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
