9
$\begingroup$

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)

$\endgroup$
1
  • $\begingroup$ Is a numerical method for solving the general case something that you might be interested to? $\endgroup$
    – Kroki
    Commented Jun 14, 2023 at 12:19

4 Answers 4

12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ For $n$ points (including $2$ or $3$) you want the radius of the minimum bounding circle, or sphere in higher dimensions. $\endgroup$
    – Henry
    Commented Jun 15, 2023 at 0:48
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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 :

P1P2P3

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.

$\endgroup$
8
  • 1
    $\begingroup$ This could be true for some of the chosen 3 points, but not all of them. What if we pick the 3 points such that they are almost in a straight line? Then by your logic the point $P$ must be positioned extremely far away from all 3 points when we could easily find a better option for $P$. $\endgroup$
    – cherrytree
    Commented Jun 14, 2023 at 11:03
  • $\begingroup$ Nice Catch , I will revise my answer , @cherrytree , & repost later ! $\endgroup$
    – Prem
    Commented Jun 14, 2023 at 11:05
  • $\begingroup$ I think if all 3 points are in the same hemisphere of the circle, the point $P$ is just the midpoint of the longest side of the triangle that is formed. Would this be right? $\endgroup$
    – cherrytree
    Commented Jun 14, 2023 at 11:18
  • $\begingroup$ It looks like there might be Points where 1 walker will reach earlier & 2 walkers will reach later though at Same time , @cherrytree , I am thinking . . . . ! $\endgroup$
    – Prem
    Commented Jun 14, 2023 at 11:22
  • $\begingroup$ The circumcenter will be the point that is equidistant between the three initial points. And if these points form an acute triangle, this will minimize the longest distance that anyone of the three has to travel. However, if they form an obtuse triangle, then the minimizing point will be the midpoint of the longest side. $\endgroup$
    – user317176
    Commented Jun 14, 2023 at 11:23
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Side note about your hypothesis, it is true that "Consider the circumcircle of every 3 consecutive vertices (only). Then the circle with the largest radius will cover the polygon.". Unfortunately, that tends to arise from an obtuse triangle. $\endgroup$
    – Calvin Lin
    Commented Jun 14, 2023 at 14:40
  • $\begingroup$ Thanks for pointing this out $\endgroup$
    – Simon
    Commented Jun 14, 2023 at 15:17
  • $\begingroup$ Are there any other cases? I don't think so. $\endgroup$
    – Peter Shor
    Commented Jun 14, 2023 at 20:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .