A (now closed) question on SO made me think about the following problem:
Given an arbirtary number of points (2D), draw a path that consists of straight lines between points, visits each point exactly once and does not intersect with itself.
I came to the conclusion that this is easy if I can chose starting and ending point:
sort points by their x coordinate use point with mininmal x coordinate as starting point connect remaining points in left-to-right order
If there are multiple points with the same x value, start with the point with minimal y value and go bottom-up. This way, no intersections can occur.
Now my question is: is this still possible if start and end point are fixed? I assume that there are well known algorithms for this problem, but my search didn't reveal any useful results.
As @hyde points out, there is no solution if more than two points are on a straight line and start/end points are not the outermost points.