@Rahul and Asquare: The algorithm could look like this:
imax = 0 // location of longest string of duplicate slopes
lmax = 0 // length of longest string of duplicate slopes
smax = undefined // value of slope
for i = 1 to n-1
for j = i+1 to n
s(j) = slope of the line through points i and j
end for j // O(n)
sort s(i+1:n) // O(n log n)
scan s(i+1:n-1) looking for the longest string of duplicates //
O(n)
when you find a string of duplicates longer than lmax,
imax = i
lmax = length of string
smax = the common slope
end scan // O(n)
end for i // O(n*(n+ n log n + n) = O(n^2 log n)
// Now you know the point imax at which you found the longest string
of duplicate slopes, and the value of that duplicated slope
j = 1
col_pts(j) = imax // array of collinear points
for i = 1 to n with i not_equal imax
slope = slope of line through imax and i
if ( slope equals smax ) then
j = j + 1
col_pts(j) = i
end if
end for // O(n)
Thus, the entire algorithm is O(n^2 log n)
Dave
On Oct 15, 2:16 am, rahul patil <[email protected]> wrote:
> On Thu, Oct 14, 2010 at 10:00 PM, Mridul Malpani
> <[email protected]>wrote:
>
> > by forming n*n pairs of points. now you have to select any 2 pair such
> > that these 2 set have atleast 1 points in common, and their slope must
> > be equal.
>
> > this will take O(n^4).
> > correct me, if i m wrong.
>
> I think Dave is correct,
>
> let us consider there are n points,
> n slopes are stored in an array like this
>
> (1,1) (1,2) (1,3) (1,4) (1,5) ..... (1,n)
> (2,2) (2,3) (2,4) (2,5) ..... (2,n)
> (3,3) (3,4) (3,5) ..... (3,n)
> (4,4) (4,5) ..... (4,n)
>
> so this will take nlogn time
> for n rows
>
> 1>
> for one row it will take logn time( having n elements)
> sort this row again nlogn time.
> and then in single traverse you will get all the colinear points
> in one row(having one point in common)
>
> nlogn [for sort] * logn [for one row slope calculation] + n
> = nlogn [for sort] * logn [for one row slope calculation]
> = n(logn )^2
>
> for n rows u will have n* n(logn )^2 = n^2 (logn )^2
>
> correct me if i am wrong
>
>
>
>
>
>
>
> > On Oct 14, 7:00 am, Dave <[email protected]> wrote:
> > > @Asquare. Yes, you are wrong. If the slope of the line AB equals the
> > > slope of the line AC, then points A, B, and C are collinear. One way
> > > to look at it is that because AB and AC have the same slope, they are
> > > parallel (if you can call coincident lines parallel), and they both
> > > contain point A. Therefore, they are coincident.
>
> > > Dave
>
> > > On Oct 13, 3:04 pm, Asquare <[email protected]> wrote:
>
> > > > @Dave -
>
> > > > Although what u have posed is correct to an extent but this will also
> > > > include cases where the line joining the points are parallel and not
> > > > collinear
> > > > So we will have to impose a check for one of the points involved
> > > > in every two same slopes to be coincident.
>
> > > > Do correct me if i am wrong..
>
> > --
> > 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.
>
> --
> Regards,
> Rahul Patil- 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.
