@Siva: The 2-d problem is just two 1-d problems. The distance function d(x,y) decomposes as f(x) + g(y). So find the optimal x as the median of the x-coordinates and the optimal y as the median of the y- coordinates.
Dave On Dec 8, 12:51 am, Sivasangari <[email protected]> wrote: > @Dave fine with the 1d prob...how about extending to 2D sir...?? > > > > On Thu, Dec 8, 2011 at 1:18 AM, Dave <[email protected]> wrote: > > @Siva: The distance function, d(x) is not differentiable at each of > > the individuals' locations, and is piecewise linear between the > > locations. The minimum will either be at a point where the derivative > > of d() is 0 or undefined. Based on this, we can say the following: > > > For the 1-d problem, if there is an odd number of individuals, the > > optimal meeting point is at the median individual. If there is an even > > number of individuals, any point between the individuals that are on > > either side of the median is an optimal meeting point. E.g., if the > > individuals are at 1, 2, and 3, 2 is the optimal meeting point, while > > if the individuals are at 1, 2, 3, and 4, any point between 2 and 3 is > > an optimal meeting point. In any case, one of the individuals' > > locations is an optimal point. > > > Dave > > > On Dec 7, 10:46 am, Siva <[email protected]> wrote: > > > Consider that there are n (finite)individuals standing at different > > > points on a line.Now we need to find the meeting point of all the > > > n .They can move either left or right and every single step is added > > > to the output . > > > > This same problem is extended for a 2D array. here they can move up > > > down left right .find the meeting point. > > > > Note meeting point neednt be the point of one of the n individuals > > > -- > > 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.
