I actually made a mistake. The function is convex and binary search works. Look up GEOMETRIC MEDIAN in Wikipedia.
-Nima On May 9, 2012 10:24 AM, "atul anand" <[email protected]> wrote: > sort p(xi,yi) on the basis of x-axis. find media of x-axis = x_median > sort p(xi,yi) on the basis of y-axis. find media of y-axis = y_median > > find distance from p(x_median,y_median) to all N points. > the distance minimum from p(x_median,y_median) is the point closest point. > > algo seems to work , but not checked all test cases. > > On Wed, May 9, 2012 at 3:27 PM, Nima Aghdaii <[email protected]>wrote: > >> 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. >> > > -- > 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.
