4
$\begingroup$

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.

enter image description here 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.

$\endgroup$
  • $\begingroup$ can these points live anywhere in $\mathbb{R}^n$? $\endgroup$ – Barcode Feb 5 at 0:38
  • $\begingroup$ Would an approximation algorithm be acceptable? For example, an algorithm that always produces non-intersecting trajectories, but the total distance of the trajectories may be up to a factor of 2 larger than an optimal solution. I don't have an algorithm for you, either exact or approximate, but I do have a gut feeling that solving the problem exactly might be NP-hard. $\endgroup$ – Aaron Rotenberg Feb 5 at 1:35
  • $\begingroup$ @Barcode yes, they can $\endgroup$ – eawer Feb 5 at 7:47
  • 2
    $\begingroup$ As long as no three points lie on a line, if the total distance is minimal, there cannot be intersections, as by the triangle inequality exchanging the starting points of two intersecting segments would decrease the total distance. Minimising total distance is a textbook case of min-cost matching. $\endgroup$ – Antti Röyskö Feb 7 at 1:11
  • 1
    $\begingroup$ If you already knew how to answer the question when no 3 points are colinear, it would have been better to tell us that from the start in the question, so we don't have to re-discover that fact and we can focus on the aspect that is posing difficulties for you. Help us help you. I suggest you edit the question accordingly now. $\endgroup$ – D.W. Feb 7 at 7:13
2
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.