Wait! Let's clarify things before shooting random guesses. First of all, which norm is used for distance? I'm assuming that it is L2 norm (Euclidean distance). The problem statement clearly mentions that the answer should be one of the given points. So, I don't see any rationale behind taking the mean!
The idea of binary search is also wrong. The function is obviously not convex. Norm itself is convex but summation is not a convex preserving operator. You can easily verify that. However Max is a convex preserving operator. So, if the problem was finding the point which minimizes the Max distance, we could use binary search. The idea of MST is way out of this topic! Common! MST might have made sense if we were talking about distances on the graph. and then what? Finding the centroid? centroid, eccentricity,... are just based on connectivity. They don't even take into account the distances! Talking of "median"... please define it first. Or just explain how you could even sort 2D points! --Nima On May 8, 2012 10:04 PM, "pacific :-)" <[email protected]> wrote: > > > On Tue, May 1, 2012 at 8:44 PM, Bhupendra Dubey > <[email protected]>wrote: > >> Find the centroid >> >> X= (x1 +x2....xn)/N >> Y=(y1+y2......yn)/N >> This will precisely be the point no need to calculate and check with >> distance. >> > @dubey : Consider this case, let there be a cluster of 4 points near the > origin and 1 point at (100,0). Then the answer would be near the origin and > not close to the centroid. "median" might make some sense. > >> >> >> On Tue, May 1, 2012 at 1:18 PM, mohit mishra <[email protected]>wrote: >> >>> Let me know if there is any bug >>> /*using centroid of plane */ >>> >>> struct point >>> { >>> int x; >>> int y; >>> }; >>> typedef struct point Point; >>> int main() >>> { >>> int n,i; >>> int d,dis; >>> float sum_x=0,sum_y=0; >>> Point centroid,final; >>> //clrcsr(); >>> printf("how many points? "); >>> scanf("%d",&n); >>> Point p[100]; >>> printf("enter X and Y cordinates of %d points\n",n); >>> for(i=0;i<n;i++) >>> scanf("%d%d",&p[i].x,&p[i].y); >>> for(i=0;i<n;i++) >>> { >>> sum_x=sum_x+p[i].x; >>> sum_y=sum_y+p[i].y; >>> } >>> centroid.x=(int)sum_x/n; >>> centroid.y=(int)sum_y/n; >>> for(i=0;i<n;i++) >>> { >>> dis=distance(centroid,p[i]); >>> if(dis<d) >>> { >>> d=dis; >>> final.x=p[i].x; >>> final.y=p[i].y; >>> >>> } >>> } >>> printf("\n The point is (%3d ,%3d)",final.x,final.y); >>> getch(); >>> return 0; >>> } >>> int distance(Point A,Point B) >>> { >>> int x,y; >>> x=(A.x-B.x)*(A.x-B.x); >>> y=(A.y-B.y)*(A.y-B.y); >>> return sqrt(x+y); >>> } >>> >>> >>> On Mon, Apr 30, 2012 at 4:34 PM, kosgi santosh >>> <[email protected]>wrote: >>> >>>> how can we find centriod of n points in a plane? >>>> >>>> >>>> >>>> >>>> >>>> Regards, >>>> Santosh K. >>>> >>>> -- >>>> 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. >>>> >>>> >>> -- >>> 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. >>> >> >> >> >> -- >> bhupendra dubey >> >> -- >> 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. >> > > > > -- > regards, > chinna. > > -- > 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. > -- 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.
