Skip to main content
1 of 4
Sven
  • 11
  • 2

Proofing convexity of total distance between two parties with one meeting point

Apologies if I´m not using the correct mathematical wording or notation. I´ll try my best in the following problem

Suppose you have a coordinate system and 5 coordinates (A1, A2, B1, B2, M) whereas M is variable and the others are fixed. The distances between them are measured in Euclidean distances.

Person A wants to go from A1 to A2 Person B wants to go from B1 to B2 But Person A needs to meet Person B at a variable meeting point M(x,y)

Let D(C1,C2) be the Euclidean distance between two coordinates C1 and C2. Let W(M,A1,B1) be the waiting time of A for B, or B for A (whoever arrives first/has the shorter distance) at meeting point M, depending on the location of A1 and B1

Then the the objective function would be Z = D(A1,M(x,y))+ D(M(x,y),A2) + D(B1,M(x,y)) + D(M(x,y),B2) + W(M(x,y),A1,B1)

I have plotted this as see that it is a convex function. I´d like to prove that. Here is how I tried to do it:

I want to build the second derivative and show it is greater 0. As I have two variables (x and y coordinate) I´d need to use Hessian Matrix and partial derivatives. But the function W(M,A1,B1) is a max() function, depending on D(A1,M(x,y)) and D(B1,M(x,y)). This max functions is somewhat problematic (at least to me). My idea is that in fact it never makes sense to wait as it would always be better to move a little closer to the other Person. As a result I determine the equation that separates A1 and B1 such that the distance from A1 and B1 to the equation is always the same. Now I know that M(x,y) must be on this equation M(y) = mx + b. Not I can insert this equation into

Z = D(A1,M(y))+ D(M(y),A2) + D(B1,M(y)) + D(M,B2)

Now I "only" need to build the first and second derivative. The problem I am struggling with is that each term D() is a root-term (coming from the Pythagoras Formula). Within that Formula I additionally have the Equation for meeting point M. I can use the chain rule, which gets ugly but I manage to do it. However, the derivative is so long/complicated, that I could not tell if this is greater 0 or not.

Do you have any idea how the problem could be simplified?

Sven
  • 11
  • 2