Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
add comment

1 Answer 1

up vote 4 down vote accepted

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).
share|improve this answer
    
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
2  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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