i just find out that after finding the convex hull we can do the rest in O(h) (See Jalaj Jaiswal's post: Computational Geometry)
On Tue, Jun 29, 2010 at 1:31 AM, Amir hossein Shahriari < amir.hossein.shahri...@gmail.com> wrote: > @Amit: in most of the algos for convex hull the result would be the points > on the hull in clockwise or counter clockwise order > now we have a point P that we want to find the farthest point from it now > imagine the list as if it's circular and the range where binary search is > applied on starts after the index of P and ends before it. in this range the > distance between the points and P increases until it reaches the maximum > distance then starts to decrease since it's a convex hull and the points are > sorted clockwise or counter clockwise > so each time you need to check the distance between P and the two middle > points to see in which direction the distance increases > i hope it's clear now > > @Jitendra: i think that Harit is right but if the points are not sorted the > worst case would be O(nlogn) > -- 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.
