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 next points or maybe does not turn (since the polygon is convex) if we do this for all points in this manner P and Q both will turn one time all over the polygon so the overall running time would be O(n)
On Tue, Jun 29, 2010 at 3:56 PM, jalaj jaiswal <[email protected]>wrote: > 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 to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > 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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
