it's obvious that these 2 points must be on the convex hull so first find the convex hull O(n) then for each point on the hull find the farthest point by binary search (since if you turn on the hull the distance to the base point increases until the farthest point then it starts to decrease) if there are h points on the hull this would be O(hlogh)
On 6/27/10, amit <amitjaspal...@gmail.com> wrote: > Hi , can anyone tell me how to find the diameter of a set of N points > i.e the distance between the 2 most farthest points efficiently.... > > -- > 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. > > -- 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.
