Minimising time taken for 3 people to walk to the same point

Question

Suppose there are $3$ people that are positioned in $3$ different places on a flat plane. Assume all 3 people walk at the same speed.

The $3$ people begin walking (in a direct path) toward a single point $P$ (which is also positioned on the flat plane), and the last person to get to $P$ takes $T$ seconds to do so.

My question is as follows:

How can we find the point $P$ such that $T$ is minimised?

Let the $3$ people begin at points $(x_1,y_1),(x_2,y_2)$ and $(x_3,y_3)$:

I first assumed that the point $P$ would just be the average of the $3$ points (By average I mean taking the average of all the $x$ coordinates and the average of all the $y$ coordinates), but by fiddling around with desmos I could see that this wouldn't be correct.

Perhaps Fermat's point might come into this question? I'm not too sure. I've spent too long on this question and any help would be greatly appreciated (It would also be interesting to see if there are solutions for $n$ points in $2$D space)

Answer 1

Attempt 1 :

When Person $P_1$ reaches $X$ first & waits for the others $P_2$ & $P_3$ , naturally it can not be the minimum time : We can move $X$ a little away from $P_1$ & closer to $P_2$ & $P_3$ to make it take less time.

In other words , minimum time is when all reach $X$ at same time. When velocity is same & time is same , then Distance must be Same.

Hence the Point $X$ we want is Equi-Distant from the 3 Points.
It is the Circum-Center of the triangle given the 3 Points.
Distance is then the radius of the Circum-Cirlce.

Attempt 2 :

Consider the Pairs of Points. Choose the Pair which has longest Distance.
Let the walkers meet at $X$ which is the Mid-Point. It take minimum time because the Straight line is the Shortest Distance between those 2 Points.
If the third Point takes less time to reach this Point $X$ , that is the minimum.
Else move $X$ on the Perpendicular Bisector towards the third Point.

Attempt 3 : Merging the Earlier Attempts

Consider this Image , where $P_1$ & $P_2$ are "stationary" while $P3$ is movable along the black line :

When $P_3$ is at $P_2$ itself , then $X_1$ (Blue line , Orange Point) , which is the Mid-Point of $P_1P_2$ , is the minimum , because Straight line is the Shortest Distance between 2 Points & all 3 walkers will reach at Same time.

When $P_3$ moves right to $P_{31}$ , $X_1P_{31}$ is still shorter , hence $X_1$ remains the minimum. Circum-Center is outside the triangle hence that is not the minimum.

When $P_3$ moves right to $P_{32}$ , $X_1P_{32}$ is still shorter , hence $X_1$ remains the minimum. Circum-Center is still outside the triangle hence that is not the minimum.

When $P_3$ moves right to $P_{33}$ , $X_1P_{33}$ is Equal to the Circum-radius , hence $X_1$ remains the minimum. Here , $\angle P_1P_{33}P_2$ is right-angle. Circum-Center lies on hypotenuse.

When $P_3$ moves right between $P_{33}$ & $P_{34}$ , Circum-Center will be minimum. The minimum Point moves on the Orange line. Circum-Center is inside the triangle , hence that is the minimum.

When $P_3$ moves right to $P_{34}$ , Circum-Center will be minimum & that will reach $X_2$. Here , $\angle P_2P_1P_{34}$ is right-angle. Circum-Center lies on hypotenuse.

When $P_3$ moves more right to $P_{35}$ , the minimum Point will move on the Black line to the Mid-Point of $P_2P_{35}$.

Summary :

(A) When Circum-Center is within the triangle , that is the minimum.
(B) Other-wise , The Mid-Point of the side closest to the Circum-Center is the minimum , which is the longest Side.
(C) The Point gradually moves between Circum-Center to Mid-Point of longest side & this Change-over occurs when Circum-Center is the Mid-Point of hypotenuse which is the longest side where we have right-angle.

Answer 2

Say the three people start at points $A$, $B$ and $C$. Wlog, let points $A$ and $B$ be the furthest apart - ie $AB\ge AC$ and $AB\ge BC$.

Both $A$ and $B$ have to reach $P$ at the same time, so $P$ lies on the perpendicular bisector of $AB$.

Say the midpoint of $AB$ is $M$. Then if $CM<AM$, it's quickest for $C$ to meet $A$ and $B$ at $M$ - ie $M=P$. If not, all three people must meet at the same time.

In summary, if the triangle $ABC$ is obtuse, $P$ is the midpoint of $AB$. If it's acute, $P$ is the circumcentre of $ABC$.

The $n$ people case is interesting - presumably convex hulls are involved but beyond that I'm not sure.

Answer 3

To tackle several cases where there are $n$ people.

Case $1$: There exist two points in the convex hull such that they form the diameter of a circle that contains the entire convex hull. Then $X$ is their midpoint. Since the time to meet up is minimized for these $2$ points, while the other points are within the circle, so they are actually even closer to $X$ and will take less time to get to $X$. (you can see that the $n=3$ obtuse triangle case is actually a special case of this)

Case $2$: When there exist $3$ vertices in the convex hull and they form an acute triangle, and that its circumcircle covers the entire convex hull. Then $X$ should be the circumcenter of that acute triangle, since then the time to meet up is minimized for those $3$ particular vertices, and since all other vertices are in the circle, they are actually closer to $X$, so it's going to take even less time for them to reach $X$.

I will try to think of other cases.

Answer 4

You are looking for the smallest circle containing N points (3 in your initial case). Center of the circle is your meeting point. Finding this circle is a well-known problem: https://en.wikipedia.org/wiki/Smallest-circle_problem

The simplest algorithm is naive - check all 3-people meeting points and select the one with the longest time. This is computationally expensive with O(n^4). There are other approaches, some are linear in time. I would probably start with Elzinga and Hearn's: "take initial points to make a circle, now keep adding other points to the current circle and expend as needed, until we picked all of them". This is conceptually fairly simple and should perform reasonably well in most cases. During class on linear programming we implemented Welzl's algorithm which might be a better pick if you are not afraid of recursion.