3
$\begingroup$

I have $n$ points on a two-dimensional coordinate plane. My goal is finding a path that visits every point once, with straight lines interconnection two points. Additionally, the angle of a line through the two prior points to a point to be connected has to be less than a certain value, say 90°. (See in the attached image)

Is there any way to prove, that for a given complete graph there is no solution connecting all points under that angle threshold if there is one greedy (see below) path that can't connect all nodes? I am searching for a sort-of mathematical proof or disprove to that.

Example of points that cannot be connected for a given path

In the image, there is a graph with 2 nodes connected already. The third node (or any other unconnected node) cannot be connected with the red line, because $\alpha > 90°$. Can I prove that there is no path connecting all nodes in this graph and in any other graph, when at least one unfinished tour can be found, that can't visit any other unvisited node?

I am happy to edit my question if I forgot sharing any additional information.

Thanks in advance.

Edit: Also, the connection between points follows a greedy principle where from each point the nearest one (that doesn't exceed the angle threshold) will be picked next.

Edit 2: Is there a tour for greedy pathfinding and an allowed angle of $\alpha \leq 90°$ (instead of $\alpha < 90°$), so that right angles will work as well?

$\endgroup$

1 Answer 1

5
$\begingroup$

No; even if you've found one path that is missing a point and can't be completed, it doesn't mean that there is no better path.

enter image description here

For example, in the diagram above, the points were arranged in the shape of a regular $9$-gon, and a solution can be obtained just by going around the circle. However, if we miss a point along the way, as in the diagram above, then going back to it at the end would require taking one of the red dashed line segments, which make too sharp an angle.


If we are not only trying to find an "incorrect" path but trying to trick the greedy algorithm into taking it, it is still possible, but a bit harder. Consider the following $10$-point arrangement:

enter image description here

On the left is a greedy tour, starting from the left vertex on the bottom and going clockwise. Near the top, it is first tricked into going to the lower of the two top vertices, because it is closer; then, it is incapable of going to the other one, because a sharp turn would be required. Then, at the end, we regret our decisions for the same reasons as earlier.

On the right is a tour showing that if we are not greedy, then we can visit all the points without taking any sharp turns. (If we replace the $9$-gon by a polygon with more sides, we can find an example where the turns in this tour are arbitrarily smooth.)

$\endgroup$
4
  • $\begingroup$ Thank you for your answer. I forgot, adding an important detail to my question; A path is selected by a greedy approach so that the nearest (least-weighted) node in the graph is selected for connection. Under this assumption, the diagram you provided wouldn't result in a failing tour. Do you know a proof/disproof for this case? $\endgroup$
    – Luqus
    Feb 11, 2023 at 20:31
  • $\begingroup$ Here is a modification of the counterexample if we are selecting the tour greedily. I hope you will not continue adding more conditions :) $\endgroup$ Feb 11, 2023 at 21:02
  • $\begingroup$ Do you think your example would still work if we said the angle has to be $\leq 90°$ instead of $< 90°$? The greedy algorithm would then select the point at the top after visiting the one directly underneath it. After that, the algorithm would fail because no other point can be added not being over 90°. $\endgroup$
    – Luqus
    Feb 11, 2023 at 21:12
  • 1
    $\begingroup$ We can also slightly nudge one of the points so that the turn angle to the point at the top is slightly bigger than $90^\circ$. $\endgroup$ Feb 11, 2023 at 21:15

You must log in to answer this question.

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