[Solved]: Possible to connect arbitrary number of dots without intersections?

ignougroup
Problem Detail: 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.

Asked By : Jasper

Answered By : FrankW

It is (almost always) possible. Let the two points be $p_1=(x_1,y_1)$ and $p_2(x_2,y_2)$. Wlog, assume that $x_1<x_2$. Denote by $q_1$ ($q_2$) the point with smallest (largest) $x$-value greater (smaller) then $x_1$ ($x_2$) (and smallest (largest) $y$, if there are multiple candidates). Then you can do the following:

  • Determine the set $S_1$ of all the points with $xleq x_1$.
  • If $|S_1|=1$, connect $x_1$ and $q_1$.
  • If $|S_1| > 1$ and all the points in $S_1$ are on the same straight line:
    • If all points outside of $S_1$ are on the same straight line, there is no solution
    • Otherwise denote by $r_1$ the point with smallest $x$-coordiate not on the straight line. (If there are multiple such points choose the one with smallest $y$-coordinate.)
    • Connect the points in $S_1$ starting with $x_1$. Connect the last of these points with $r_1$ and (if $r_1 ne q_1$) connect $r_1$ with $q_1$.
  • If $|S_1| > 1$ and the points are not all on one straight line, determine the convex hull of $S_1$.
    At least one of the neighbours $n_1$ of $p_1$ on the convex hull can be reached from $q_1$ without intersecting the convex hull.
    • Draw a (reverse) path from $q_1$ to $n_1$ and then along the convex hull to the point with smallest $x$. Continue in left-to-right-order (skipping points already included) until $p_1$.
  • Analoguously connect the points with $xgeq x_2$.
  • Connect the points with $x_1<x<x_2$ (i.e. from $q_1$ to $q_2$) in left-to-right-order (ignoring $r_1$ resp. $r_2$, if applicable).
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23671