Minimizing total distance traveled by points in points cloud transformation

Question

I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting coordinates to the destination ones so that the total distance, traveled by all points is minimal.

There is one important restriction - points' trajectories should not intersect (so, trajectories could be curvy). To handle this, we may introduce some ε to denote the minimum distance between two trajectories, after which they will be considered intersecting.

Non-intersecting trajectories can be changed in favor of non-colliding points (the distance between several points can't be smaller than ε at the same moment of time) if that makes the task easier to solve (if not - let's stick to the original conditions). In such a case maximum point speed, V, should be introduced.

More than 2 points may lay on a line (e.g. 2 starting points and 2 destination ones may be collinear).

For the particular case described at the picture, the minimal path will look like A -> F + B -> G + C -> H + D -> I + J -> E.

Solutions that came to my mind:

• The greedy approach will not work, because if we start from point A and choose the nearest destination point, we'll end up with E moving to F, which is far from being optimal.
• Brute dynamic programming solution will result in something like O(n!) complexity, which is not really acceptable.

None of those solutions save me from intersecting trajectories.

My gut tells me, that some kind of gradient descent may be useful for this task, but I can't figure out how to apply it to this task.

What I need is not a working code, but advises or directions to related topics/articles/papers which will help me to understand how to solve this task.

P.S. I saw Assign m agents to N points by minimizing the total distance and Given 2 sets of n points: minimize sum of traveled distances but wondered how this task can be handled after the introduction of the aforementioned trajectory-related restriction.

Answer 1

If the trajectories must be lines and $\epsilon$ is small enough, the problem can be solved with min-cost matching. If all coordinates are integers with absolute value bounded by $H$, then two disjoint intervals with integer endpoints have distance at least $\frac{1}{4H}$ from each other. Hence if $\epsilon$ is less than this value, it might as well be 0.

Take any four points $A, B, C, D$ and assume that there exists a line segment connecting $A$ and $B$, one connecting $C$ and $D$, and that these line segments intersect at point $X$. Then $|A - B| + |C - D| = |A - X| + |B - X| + |C - X| + |D - X|$. Triangle inequality is strict when the three points do not lie on the same line, so if not all of $A,B,C,D$ are colinear, we can exchange the startpoints of the segments to decrease their total length. Thus, if no four points lie on a line, the minimum total length solution doesn't have intersecting line segments.

To find the minimum total length solution, we use min-cost matching, with cost $|A - B|$ to match points $A$ and $B$ (assuming one of $A$ and $B$ is a starting point, and the other is an endpoint).

To handle the case where some four points lie on a line, we just disallow matching $A$ and $B$ if some other point lies between them. Matching in this case is not always possible, for example if we have two startpoints, then two endpoints on a line.

Answer 2

Just a visual idea: Get all the segments possible, and remove all the crossing ones. Their number should be greatly reduced. Then apply brute-force algorithm, or smarter ones.