* Monday:    all-pairs shortest path.
* Wednesday: computational geometry (nearest neighbor, near neighbor).

* Today:     more computational geometry (convex hull).

---------------


CONVEX HULL 
-----------

Given:  a set of n points in the plane.
Output: the smallest CONVEX shape including them all.

a shape S is _convex_ iff
  for all points x, y in S,
    the line connecting x and y is also in S.

(note that without the "convex", this is trivial.
 just connect the points.)



<< draw an example >>

"stretch a rubber band around all of the points, and let go."


BTW, why do we care?  
     In some sense, this is the "sort" of computational geometry.
     used as a subroutine all over the place.
     also useful on its own.

     one application:
     (if you care about applications; I don't care if you don't care.)
       collision detection.
       if you're animating and you want to detect when two objects intersect
         (because they're going to bounce off each other, or whatever)
       then typically you use the convex hull as a preprocessor.

       maintain convex hulls of each body.
       if convex hulls intersect, then compute whether the bodies themselves
         actually intersect.
       (typically very expensive to compute actual intersections.)



So, let's develop an algorithm for this problem.

Here's a first idea:

 * find me a point that MUST be contained in the convex hull.
 * find me the next point counterclockwise from that one.
   
   how do you do that?
   given a point x, want to find the point y with the 
   minimum (polar) angle to x.

 * repeat.

This is the "gift-wrapping algorithm" (JARVIS'S ALGORITHM).
 
Take wrapping paper, and pull it against the left side of the point
set.  Pull counterclockwise until you hit another point.  Fix that
point.  Repeat.

What's the running time?

O(n * h), where h = |convex hull|.
at each vertex of the CH, find the minimum angle.
O(1) time to compute each angle.

This is often good, because in practice the convex hull is often small..


Note: this is an OUTPUT-SENSITIVE algorithm.       
  running time depends on the size of the correct answer.
  will see more in lecture on Monday.

-------------------------

-------------------------
GRAHAM'S SCAN.

Here's another algorithm for convex hull.

Maintain a stack of candidate points.
Push candidate points onto the stack.
Pop every point not in the CH off the stack.
Result:  stack contains CH points in clockwise order.

1. Let p[0] be the bottom-most point (min-y), breaking ties to the left.
2. Let p[1..m] be the remaining points, sorted by increasing polar angle
   counterclockwise from p[0].
3. push p[0], p[1], p[2] onto S.
4. for i:=3 to m
     while the angle from NEXT-TO-TOP(S) to TOP(S) to p[i] is a nonleft turn
	POP(S).
     PUSH(p[i]).
5. return S.


<< redo the example >>

For simplicity, assume no two points have the same polar angle with p[0].
(Doesn't matter; read the book for the slightly more complicated version.)

Loop invariant:  after the iteration i of Graham-Scan, S = CH(p[0..i]).

* obviously true at iteration 3.  (three points are their own CH.)
* for a later iteration i:
    let p[j] be on top of the stack just before we push p[i].

    * then, by the IH, S = CH(p[0..j]).  
    (this is exactly what the stack looked like after iteration j.) 

    * after we push, S = CH(p[0..j] \cup {p[i]}).
    (just have to "add" p[i].
     p[k] p[j] p[i] is a left turn, else would have popped p[j].)

    * CH(p[0..j] \cup {p[i]}) = CH(p[0..i]).
      aka, every point we popped was "safe" to pop.
    (if pop p[t] when p[r] was second in the stack,
     then p[t] is in the triangle p[r], p[i], p[0].
     So safe to pop.)

  thus S = CH(p[0..i]).

Therefore the algorithm is correct.


Running time of Graham's Scan:

* O(n log n) to sort.
* Everything else is easy, except the while loop.
   * Might pop as many as Theta(n) points from the stack in an iteration.
   * n iterations.  
   * So O(n^2).

  But!  Each point is pushed once.
	Each point is popped at most once.
 
  So O(n) time for while loop!
  (amortized analysis -- aggregate method.)


---------------------
Lower bound:

can't do convex hull faster than O(n log n).
why??

given A[1..n] that you want to sort,
build points 
      (A[i], A[i]^2).
find convex hull.
read off sorted order from the CH!

If you could do CH in o(n log n),
then you could sort in o(n log n).