CODEWITHSUNDEEP
algorithm
Alcott
Alcott

Reputation: 18595

choose a point which minimizes the sum of distances between it and other points in set

I read a post which talks about pretty much the same problem. But here I simplify the problem hoping that a concrete proof can be offered.

There is a set A which contains some discrete points (1-dimension), like {1, 3, 37, 59}. And I want to pick one point from A which can minimize the sum of distances between this point and others.

There might be a lot of posts out there, and my problem is just the 1-d version of those, and I know how to prove it if A is not discrete, but I fail when A is discrete like above.

Plz offer me the answer with concrete proof, thanks.

Upvotes: 2

Views: 6446

Answers (3)

Paul Hankin
Paul Hankin

Reputation: 58359

Since between points the total-distance function is linear and the distance-function is continuous everywhere, the minimum must be attained at one of the points in the set. So you can restrict A to be in the given set.

Here's a graph for the total-distance function from the points {-3, 1, 2, 5} as an example: Graph of distance function

Say there's L points to the left, and R to the right of A.

Moving one point to the right changes the distance by d * (L + 1 - R) (where d is the distance to the next point). Similarly, moving one point to the left changes the distance by d * (R + 1 - L).

The points that minimize |L-R| are where this distance is minimized. That's either the median (if it's in the set), or either of the two adjacent points to the median if it's not.

Upvotes: 2

Mihai8
Mihai8

Reputation: 3147

Considering Fastest way to find minimum distance between points question try to take a look to closest pair of points problem.

Upvotes: -1

Joachim Isaksson
Joachim Isaksson

Reputation: 181067

Not a strictly (or even loosely) mathematical proof, if that is what you need, you're most likely asking in the wrong place :)

Let's call the 1D coordinate x and let's say raising x is moving to the right. The point you're looking for is mx.

  • If mx has more points to the right than to the left, moving mx to the right will raise the distance to the fewer points to the left and lower it to the more points to the right which will lower the average distance.

  • In other words, mx cannot have fewer points to the left than to the right, if there are, there is a way to lower the average.

The converse is also true.

If the number of elements is odd, the only point fulfilling the above requirement is the median.

If the number of elements is even, any point between the two mid elements will fulfill the condition.

Upvotes: 6

Related Questions