Bill Thies
thies@mit.edu
http://cag.lcs.mit.edu/~thies/6.046

Office hours:  Sat 1-3pm
               * Mon 7-9pm (Next week only)

Announcements:
 - MANDATORY LECTURE Wed.
 - Take-home test, Wed-Mon
 - PS 6 back Monday in lecture

Today: Convex hull

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

At end of last recitation:

Can run shortest-paths in DAG in O(V+E) time [CLRS p.592]

--------------------------------------------------
BACKGROUND

Given vectors (points) p1, p2, determine whether p2 is clockwise or
counterclockwise rotation from p1

  |   p2 = (x2, y2)         |  p1 = p2    -- p1 x p2 = 0
  |  .                      |  /
  |    . p1 = (x1, y1)      | /  . p1     -- p1 x p2 > 0 (counter-clockwise)
  |                         |/               p1 x p2 < 0 (clockwise)
  -------                   -------------

Use cross product:

                (x1 x2)
  p1 x p2 = det (y1 y2) = x1*y2 - x2*y1

The sign of cross product is also given by right-hand rule.

Given points p1, p2, p3, determine whether path p1->p2->p3 takes "left
turn" or "right turn" at p2:

  |           p3
  |          .
  |    . p2          Compute (p3 - p2) x (p2 - p1) -- if > 0, then right turn
  |                                                   if < 0, then left turn
  |   . p1
  |
  ------------------------

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

Def.  A set is convex if every line segment connecting two points in
the set is fully contained in the set.

  ....................
   ......           .
        .         .   ...
        .       .    .  .          [ regular pentagon ]
  .......        ....  .  
  .                   .   
   .......        ....
          .........

     (Non-convex polygon)           (Convex polygon)

Def.  Convex hull of set of points P is smallest convex polygon
containing P.

      [ draw points, then connect in convex hull ]

<< Give intuitive explanation with rubber band and nails. >>

--------------------------------------------------
GRAHAM SCAN ALGORITHM

<< kicked off the field of computational geometry.  Back in 1972. >>

Intuition:
- Draw simple* polygon.     (* actually, polygon is "star-shaped",
- Eliminate points at          which means all vertices are visible from p0.
  concave angles	       Some simple polgyons will not work.)

   x                     x
             x
                               x
        x
                   x        x
                               x
     x

--------------------------------------------------
GRAHAM-SCAN(Q) // returns convex hull of Q, in counter-clockwise order
1. Let p0 = point in Q with min y coord. (break tie by min x coord.)
2. Sort remaining points in Q by polar angle from p0 (break tie by distance from p0)
   Store result in list <p1, p2, ..., pn> (sorted counter-clockwise)
3. Push(p0, S)
4. Push(p1, S)
5. Push(p2, S)
6. for i <- 3 to n {
     while angle SECOND(S)->TOP(S)->pi is right or straight {
        Pop(S)
      }
      Push(pi, S)
    }
7. return S

--------------------------------------------------
EXAMPLE (see powerpoint animation for details)

   x                     x
             x
                               x
        x                                  p2
                   x        x              p1
                               x           p0
     x                                     S 
  p0

--------------------------------------------------
CORRECTNESS

Loop invariant: At start of iteration i, S holds convex hull of points
p0...p(i-1).

Initialization: 
   three points, forms its own convex hull  
    << step 2 removes points collinear from p0 >>

Maintenance:  
   Before i'th iter: <p0, ..., pj, pk, ..., pl>
   After i'th iter:  <p0, ..., pj, pi>

   Show:  1) pi is on convex hull of <p0, ..., pj, pi>

               [ draw convex hull ]

          << By induction, Qj was convex hull of <p0, ..., pj> >>
          << Must add pi to cover segments p ->p0, pi->pj >>
          << Adding pi is sufficient due to left-hand-turns >>

          2) pk, ..., pl are NOT on convex hull

            << add in edges.  They made right-hand turn.  Thus
               segment from pi would NOT be included in set. >>

            << Equivalently, they are contained in
               triangle, so cannot be on outside edge. >>

Termination: i=n+1, so S holds convex hull for p0...pn

--------------------------------------------------
RUNNING TIME

Go back and annotate algorithm:

              GRAHAM-SCAN(Q) // returns convex ...
O(n)          1. Let p0 = point in Q with min  ...
O(n lg n)     2. Sort remaining points in Q by ...
                 Store result in list <p1, p2, ...
O(1)          3. Push(p0, S)
 |            4. Push(p1, S)
 |            5. Push(p2, S)
O(n)          6. for i <- 3 to n {
  w.c. O(n)         while angle SECOND(S)->TOP ...
                      Pop(S)
                    }
                    Push(pi, S)
                  }
              7. return S

<< So O(n^2)?  How can we do better for step 6? >>

Every item is pushed once, popped at most once
 ==> Step 6 is O(n)

Overall runtime = O(n lg n)

--------------------------------------------------
JARVIS'S MARCH

- Computes convex hull of n points in O(nh) time
   - h = # points in convex hull
   - "output sensitive" algorithm: 
     runtime grows with size of output

    [ run example algorithm ]

  << analogy to gift wrapping >>

Usually faster than Graham's scan in practice
  - Whenever CH(Q) = o(lg n)
  - Worst case for Jarvis:  all points lie on circle

--------------------------------------------------
| We didn't cover the following in recitation:
| 
| JARVIS(Q)
| 1. Let p0 = bottom-left point
| 2. v = p0
| 3. do {
|    S <- S U {v}
|    Sort points by polar angle from v
|    v <- point with max polar angle
|    } until v = p0
| 
|   << note: cross product comparison considers "clockwise" only in
|   range [0,pi].  thus, need two scans, left and right, if you don't
|   want to bother with extra work to calculate the angles in range
|   [0,2pi]. >>
| 
--------------------------------------------------
| 
| If extra time:  O(n lg n) lower bound in comparison model
| 
| Reduce to sorting.  Map i -> (i, i^2) and do convex hull.