Six of us were having dinner in a restaurant in on Friday evening. We had travelled from different parts of London and had travelled different decisions. I started thinking about where we could have met to minimise the total distance we travelled.
In other words, given a set of friends and their starting points and assuming we measure straight-line distances - ignore roads and hills - there must be at least one point that requires the least total distance to be travelled in order for everybody to meet. Furthermore, there may be more than one such point. As an example, consider just two friends: any point on a straight line between them would be a meeting point that satisfied my requirement that the total distance travelled is miminised.
My question is: given an arbitrary number of friends and their starting points, what can we say about the set of points representing minimum total distances travelled? In particular, will its points necessarily be connected to each other or could they be dispersed?
5 comments:
This seems to be the problem examined in n-Ellipses and the Minimum Distance Sum Problem by Junpei Sekino. Haven't read the paper, but the abstract indicates there's a single solution (unless there's an even number of people, all on a line).
My intuition is that for any apart from 2, there is a single point at the weighted mid point - as from that point any movement will increase the distance for the further away ones more than it will decrease the distance for the closer ones.
Just an intuition though, no proof.
Simple solution for 3 points on a line - the minimal total distance is the middle point.
Oops, lost the link for a few days...
This is ugly and doesn't tell you where the point is, but I think I have an argument that one of the following must be true:
A) The solution is a line segment, in the case that all the points lie on a line and there's an even number of them (the segment joins the 'middle' two).
B) The solution is a unique point
C) There's no solution, whichever point you choose, you can do better.
(I'm pretty sure C never happens, but I don't know how to do analysis in more than one dimension).
Suppose there are two distinct solutions P and Q (i.e. B and C fail). Now set up a co-ordinate system so P is at (0,0) and Q is at (1,0), and call the points (x_i, y_i).
Consider the distance from (x,0) to one of the points (x_i, y_i) as a function f of x.
f(x) = sqrt( (x-x_i)^2 + y_i^2 )
If y_i = 0, this is |x-x_i|. f'(x) exists and is continuous everywhere except at x_i, and is (non-strictly) increasing.
If y_i ≠ 0, the second derivative exists everywhere and is y_i^2/((x-x_i)^2 + y_i^2)^(3/2) > 0, so f'(x) is again increasing.
In either case f has at most 1 discontinuity and 1 undefined point, and they're at x=x_i.
Now consider the total-distance function F(x) = Sum{f(x)}. F'(x) is undefined/discontinous at only finitely many points, and it's increasing. Let A be the right derivative at zero of F.
Because the derivative is piecewise continuous and increasing, the A = the right limit at 0 of F'(x) ≤ F'(x):(0<x<1) ≤ the left limit at 1 of F'(x) = the left derivative at 1 of F(x) = B.
Now if A < 0 then F(e) < F(0) for some small e > 0, and if B > 0 then F(1+e) < F(1) for some small e < 0, both contradictions since 0 and 1 are minimal total-distance points. So 0 ≤ A ≤ B ≤ 0, so F'(x) = 0 everywhere it's defined.
This means F''(x) = 0 where defined, so there can be no points not on the x-axis as these produce strictly positive terms.
Given that the points are all on a line, it's easy to show that a point on the line is a solution if and only if there are an equal number of the points on each side of it, and the result follows.
Good grief!
(Very clever, though :-) )
Post a Comment