# Possible to connect arbitrary number of dots without intersections?

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.

-
Do I misunderstand the problem, or is 3 points on a straight line with middle point as start or end point a trivial example of impossible scenario? Or does this case not count as having intersections and/or visiting the mid point twice? –  hyde Apr 11 at 18:40
@hyde You are right. If all the points are on a single straight line and start or end point are in the middle, there is no solution. However, this is the only scenario without a solution. –  FrankW Apr 11 at 18:59
Another note, if there are 5+ points on straight line and exactly one elsewhere, an impossible scenario is also possible. Other arrangements of points, not sure if they're always solvable, but I wouldn't be comfortable just assuming so. –  hyde Apr 11 at 19:33

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 $x\leq 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 $x\geq 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).
-
Thanks! Since I'm not a native english speaker, are there differences between "in" and "on" the complex hull? What are the neighbors of $p_1$? Is $(n1)$ the only other neighbor (see imgur.com/NWCDRe4)? I think the last point must be "Connect the points between $q_1$ and $q_2$. –  Jasper Apr 11 at 13:34
@Jasper I'd say "on" the convex hull only covers the points on the border, while "in" may also include those inside the surrounded area. $(n_1)$ is indeed the only other neighbour of $p_1$ on the convex hull. (And your picture fits the algorithm.) For the last bullet, your wording is almost equivalent to mine. (One might read your wording as excluding $q_1$ and $q_2$.) –  FrankW Apr 11 at 14:05
Does this algo have a canonical name? What is the original source? –  Jasper Apr 11 at 17:00
I came up with the algorithm myself and have not done any research if it was previously known. –  FrankW Apr 11 at 18:50
@Jasper in 574 chars: Let p, p' be start and end dots, with p left of p'. Let q, q' be leftmost and rightmost dots. Let r, r' be leftmost and rightmost dots between p and p'. The convex hull of all dots left of p, p included, includes q. The hull has 2 dots next to p. For at least one, say s, the segment sr does not cut the hull. Connect r to s, then s to q through the part of the hull not including p. Connect q to p through all the remaining unused dots left of p as with the left to right algorithm . A mirror procedure connects p' to r'. Connect r to r' with the left to right algorithm. –  babou Apr 12 at 11:23