Dave, This sounds a bit like quibling. Nearly all computational geometry algorithms assume real coordinates. Floating point implementation is a separate problem. This is _algorithm_ geeks... ;-)
Nonetheless, if the coordinates are rational, then you can choose A,B,C integer as I said. Exact hashing works fine for integers. Finally, even if you are worried about floating point implementation, there is no reason that a hash function for floating point triples cannot compute the same hash for triples that are "almost equal". The way I defined the triples makes this straightforward. I'll note in addition that if coordinates are given in floating point, then your own algorithm needs some tweaks because comparing slopes is numerically unstable for near-vertical lines. Cheers... On Oct 26, 12:04 am, Dave <dave_and_da...@juno.com> wrote: > @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.-Hidequotedtext - > > > > >>> > - 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.-Hidequoted text - > > > > - Show quoted text -- 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.
