title: Gift Wrapping Algorithm (Jarvis March) - Single Run using Cross Product
body: <p>In the well known "Introduction to Algorithms - 3rd edition" book the Gift Wrapping Algorithm for finding the Convex Hull of a set of points in 2D space is described as requiring either:</p>
  
  <ol>
  <li>2 runs for finding the left and right chain of the convex hull separately</li>
  <li>sorting the polar angles with respect to the last segment of the convex hull</li>
  </ol>
  
  <p>in order to use the Cross Product trick for sorting polar angles and getting correct results. </p>
  
  <p>However, it seems to me that it is enough to consider just the latest point of the convex hull. Here is my approach (assuming no 3 collinear points appear in the input):</p>
  
  <pre><code>pLast = latest found point of the Convex Hull
  &lt;p1, p2, ..., pk&gt; = points that are not (yet) in the Convex Hull
  pNext = the next point of the Convex Hull (trying to find this)
  
  pNext = p1 
  for i=2 to k 
     if (nonLeftTurn(pLast, pNext, pi) == true)
        pNext = pi
  </code></pre>
  
  <p>Here nonLeftTurn(p1, p2, p3) return true if p3 is to the right of oriented line p1->p2:</p>
  
  <pre><code>nonLeftTurn(p1, p2, p3):
     if ( (p2 - p1) x (p3 - p1) &lt;= 0)
        return true
     else
        return false
  </code></pre>
  
  <p>It seems to me that this approach is correct. What am I missing? Could you please provide a counter-example as I'm not able to find one.</p>
  
  <p>Thanks!</p>