5

Problem statement: We are 3 friends at 3 different locations $A, B, C$ and want to reach a location $D$. Each person will take a separate cab to a common meeting point $E$, and then take a single cab from $E$ to $D$.

How can I find the point $E$ which minimizes the total distance traveled by all four cabs?

Martin Sleziak
  • 53,687
amitchhajer
  • 173
  • 6
  • Your problem isn't very well defined and some users of this site will take issue with that. People $A$, $B$, and $C$ need to reach a point in how similar of a time? What is the relative importance of them meeting close to $D$ versus minimizing the distance traveled by each person? – Mike Pierce Jan 12 '16 at 05:38
  • They all have to reach a point X which is close to D, so that all of them have to travel least. – amitchhajer Jan 12 '16 at 05:41
  • 1
    But if you want to minimize the distances that each person travels, they should just go straight to $D$. – Mike Pierce Jan 12 '16 at 05:42
  • sorry my bad completely, was in between and wrote the above comment. Basically, think of a scenario where they all are taking cabs and I want to minimize the cost of cabs they are taking. Which depends on number of cabs and time they are travelling. I want to minimize, (number of cabs + time for each of them) by making them travel some distance in separate cabs and then taking one single cab. Sorry about the above comment. – amitchhajer Jan 12 '16 at 05:51
  • @amitchhajer I've taken a stab at clarifying the problem statement to reflect the problem you intended to ask. Please edit again if I got something wrong. – user7530 Jan 12 '16 at 06:10
  • Are there any limits to the paths taken by the cabs? Must they travel along a grid of streets? Or can they travel on any straight path? – JRN Jan 12 '16 at 06:17

1 Answers1

3

If $E$ is the common meeting point, you are trying to solve

$$\min_E \|A-E\| + \|B-E\| + \|C-E\| + \|D-E\|$$

The solution to this optimization problem is the geometric median $E$ of the three friends and the destination point $D$. In general computing the geometric median is not straightforward, but in the special case of four points there is an easy algorithm:

1) If one of the four points lies in the triangle formed by the others, take $E$ to be that point. In this case all friends travel directly to $D$ (if this is the inside point) or two friends first travel to the third and then all friends travel together to $D$.

2) Otherwise, the four points form a quadrilateral. Draw the diagonals and take $E$ to be the intersection point.

It's not so obvious why this algorithm correctly identifies the median; proofs are given here.

Martin Sleziak
  • 53,687
user7530
  • 49,280