Finding the closest point from a set of points on plane

Given n points on a 2-D plane, what is the point such that the distance from all the points is minimized? This point need not be from the set of points given. 开发者_C百科Is it centroid or something else?

How to find all such points(if more than one) with an algorithm?

This is known as the "Center of Distance" and is different from the centroid.

Firstly you have to define what measure of distance you are using. If we assume you are using the standard metric of d=sqrt( (x1-x2)^2 + (y1-y2)^2) then it is not unique, and the problem is minimising this sum.

The easiest example to show this answer is not unique is the straight line example. Any point in between the two points has an equal total distance from all points.

In 1D, the correct answer will be any answer that has the same number of points to the right and the left. As long as this is true, then any move to the left and right will increase and decrease the left and right sides by the same amount, and so leave the distance the same. This also proves the centroid is not necessarily the right answer.

If we extend to 2D this is no longer the case - as the sqrt makes the problem weighted. Surprisingly to me there does not seem to be a standard algorithm! The page here seems to use a brute force method. I never knew that!

If I wanted to use an algorithm, then I would find the median point in X and Y as a start point, then use a gradient descent algorithm - this would get the answer pretty quickly. The whole equation ends up as a quadratic, so it feels like there ought to be an exact solution.

There may be more than one point. Consider a plane with only two points on it. Those points describe a line-segment. Any point on that line-segment will have the same total distance from the two end-points.

This is discussed in detail here http://www.ddj.com/architect/184405252?pgno=1

A brute force algo. might give you the best results. Firstly, locate a rectangle/any quadrilateral bounding the input points. Finally, for each point inside the rectangle, calculate distance from other points. Sum the distances of the point from the input set. Say this is the 'cost' of the point. Repeat for each point and select point with min. cost.

Intelligence can also be added to the algo. it can eliminate areas based on average cost, etc...

Thats how I would approach the problem at least... hope it helps.