Points moving towards the nearest point, where will they meet?

580 Views Asked by At

Consider an arbitrary number of distinct points in some $n$ dimensional space whose locations are exactly known. Every point is moving towards its nearest point simultaneously, at constant speed. If multiple points meet in a point, that's the new single point and the game continues. What will be the final point where all the points will eventually meet?

What are the methods to finding the final meeting point?

What if a point is equidistant to multiple points? Then it moves towards all of them :

If a point is equally distant from two points, it moves towards the line determined by those two points. If a point is equally distant from three points, it moves towards the plane determined by those three points. Similarly for more equidistant points in some $n$-space.



$(n=1)$

If we are observing points on a line, then if $T(x_1)$ and $T'(x_2)$ are the outmost points (all other points are on the line segemtn $TT'$), then the final point will always be in the midpoint $P(\frac{x_1+x_2}2)$, no matter how many points and where are located on that line segment.

For the cases when a point is equally distant from two closest points, it simply won't move as it is already on the line determined by those two points, which now will meet at it.


$(n>1)$

If we are observing points on a plane, if three points are equally distant from one another, then they will end up in the center of that equilateral triangle, made of those three points. (Since each is moving towards opposing side)

But already at three points on a plane, if we have a pair of points meeting in the middle, and a third point far away gravitating towards one of those two points, its path will be a curve until the two distant points meet, and then its path will continue in a straight line towards the merged point.

enter image description here

I'm not sure how to show where exactly the final point will end up relative to the triangle.
(white point on the picture is the meeting point; blue points are the starting points.)

However, if the third point $C$ is equally distant from the two paired points $A,B$, then it is simple to find the ending point as we don't have curved paths. The paired points will meet at the midpoint $P$ of $AB$, and $C$ would've traveled distance $AB/2$ towards $P$ by this point, to $C'$. Now final point is at the midpoint of $PC'$.

But I'm just observing certain cases and not sure how to approach this generally; as I'm already not sure how to handle arbitrary amount of points on arbitrary locations in the plane.

Example of paths; Random $20$ points on a plane, where red point is $(0,0)$ and white point is the point where all points eventually meet:

enter image description here

1

There are 1 best solutions below

0
On

Solution for $n = 3$ (that can be extended partially)

Label the points $A,B$ and $C$ such that $\overline{AB} < \overline{AC} < \overline{BC}$ and move them such that $A = (0,0)$. Transform the coordinates for $B = (b_x,b_y) \mapsto (0,1)$

$$T = \pmatrix{b_y & b_x \\ -b_x & b_y} \qquad T^{-1} \cdot C = \pmatrix{x_0 \\ y_0}$$

$\hspace{4cm}$

$A$ and $B$ will meet at $(0,0.5)$. According to this $C$ will have moved to the following coordinates

$$c_x = x_0 \sqrt{\frac{1}{k} \operatorname{W} \left( k \exp{\left( k - \frac{2}{r_0 - y_0} \right)} \right)} \qquad k = \frac{r_0 + y_0}{r_0 - y_0} \quad r_0 = \sqrt{x_0^2 + y_0^2}$$ $$c_y = \frac{1}{4} \left( (y_0 + r_0) \left( \frac{c_x}{x_0} \right)^2 + 2 \, (y_0 - r_0) \ln{\left( \frac{c_x}{x_0} \right)} + 3y_0 - r_0 \right)$$

We then transform back to obtain the coordinates of the final point

$$T \cdot \left[ \frac{1}{2} \pmatrix{c_x \\ c_y + 0.5} \right] = \pmatrix{x \\ y}$$

This also applies to $n = 4$ if there are two pairs of points that don't influence each other

$\hspace{4cm}$