We can calculate the centroid of all d points and then calculate their individual distances from it .The point with the minimum distance will be the answer. TC :O(n)
Regards, PAYAL GUPTA On 4/25/12, Navneet <navneetn...@gmail.com> wrote: > We cannot do it without computing distances of each node from all other > nodes. So to begin with, construct a matrix representation of the graph > with distances filled in for every pair of points. > > Proceed to calculate the minimum spanning tree of such a weighted graph. > Kruskal's and Prim's are two well known algorithms to do that. Such a point > should lie on this spanning tree. > > Not very sure how to quickly find the desired point on MST, but problem > becomes easier with MST. > > > On Wednesday, 25 April 2012 11:10:38 UTC+5:30, tech coder wrote: >> >> Given N points(in 2D) with x and y coordinates. You have to find a >> point P (in N given points) such that the sum of distances from >> other(N-1) points to P is minimum. >> >> -- >> >> Regards >> "The Coder" >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/rJZk24xBTqYJ. > To post to this group, send email to algogeeks@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 algogeeks@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.
