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.

  • $\begingroup$ 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? $\endgroup$
    – hyde
    Apr 11, 2014 at 18:40
  • $\begingroup$ @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. $\endgroup$
    – FrankW
    Apr 11, 2014 at 18:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – hyde
    Apr 11, 2014 at 19:33

1 Answer 1


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).
  • $\begingroup$ 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$. $\endgroup$
    – Jasper
    Apr 11, 2014 at 13:34
  • 2
    $\begingroup$ @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$.) $\endgroup$
    – FrankW
    Apr 11, 2014 at 14:05
  • $\begingroup$ Does this algo have a canonical name? What is the original source? $\endgroup$
    – Jasper
    Apr 11, 2014 at 17:00
  • $\begingroup$ I came up with the algorithm myself and have not done any research if it was previously known. $\endgroup$
    – FrankW
    Apr 11, 2014 at 18:50
  • $\begingroup$ @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. $\endgroup$
    – babou
    Apr 12, 2014 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.