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.
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?
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.
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:
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.)