number the elements in clockwise order from 1..n suppose n is 12
then start from a point here we start from the point 1 then we find the
farthest point from it in O(n) suppose that's point 5
now if we want to find the farthest point from point 2 since we moved
clockwise the farthest point must turn
@Amir
i m not able to understand how complexity is o(n) if u r doing for all
vertices...plzz elaborate
--
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 g
we can only do this if the shape is convex and the points are sorted
clockwise or counter clockwise
suppose that the points are sorted clockwise
start from a point P find the farthest point from it Q O(n)
now move P to the next point after P in clockwise turning
the Q will turn clockwise to the nex
how to find two vertices of a polygon which are farthest from each other in
linear time
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email
Hi all,
I am fixed in this problem. It has also been asked in Google
interviews.
Given n points in a plane, suggest an algorithm to find maximum no. of
collinear points ?
Thanks in advance...
--~--~-~--~~~---~--~~
You received this message because you are subscrib
