Problem definition
	Given a bunch of points
		We'll focus on 2D, but also talk some about 3+D
	Find polygon s.t. vertices are in given points, and contains all points
		A sequence of points
		What can you say about the shape, in general?  -- convex

	Useful as a common building block in graphics algorithms
		E.g., set diameter, smallest enclosing rectangle,
		finding regression line
	Illustrates some useful ideas of graphics/geometric algorithms

Brainstorming
	Approach ideas?

	How can we find ONE point of hull?
	Given one point, how can we find "next" point?

We'll focus on three algorithms
	Includes one not in textbook, and one that is a variation on
	what is in textbook

Jarvis' March = Giftwrapping (1973)
	Illustrate with example while giving algorithm.

	Find one point of hull -- choose one with maximum x value
	Consider reference line containing point, parallel with y axis
	Repeat
		Choose point that is minimum counter-clockwise angle
		from reference line

			Aside: How? How to compute angles?

			Computing angle via trig is expensive.
			Sufficient to compute based upon cross products:
			E.g., first assume two points & origin:
				p2 X p1 = x2y1 - x1y2
				          is negative if p2 is ccw from p1
				Examples
				Not useful to compare p2 X p1 and p3 X p1,
				instead must compute p3 X p2
			More generally, consider (p2-p0) X (p1-p0)

		Reference line is now the last line segment
	Until found point is starting point

	Analysis
		O(points on hull * points to compare angles)
		O(n*n)

		Or, more usefully,
		O(h*n)
			An "output-sensitive" measure.

Graham's Scan (1972)
	Rather than sort-of-sorting points multiple times, let's sort once

	Break overall computation into two halves -- upper & lower hulls
		Small convenience that simplifies some math
		We'll describe upper hull.  Lower hull is same idea.

	Illustrate with example while giving algorithm.

	Sort points by x coordinate
		In ties, can simply ignore points with non-maximal y
	Choose point with maximum x value
	Choose point with next smaller x value
	Repeat
		Choose point with next smaller x
		While previous three points form right-hand angle
			(computed via cross product)
			Delete penultimate point
	Until found point has minimum x value

	Analysis
		O(sort points + points * average time per point)

		A simple aggregate analysis like our previous stack
		example shows that the average time per point is
		constant.

		O(n log n + n) = O(n log n)

Compare Jarvis' & Graham's running times
	O(nh) vs. O(n log n)
	Depends on how many points on hull

Divide-and-Conquer
	Again, for simplicity, separate upper and lower hulls.

	Illustrate with example while giving algorithm.

	If #points <= 3, compute upper hull explicitly.
	Partition points in half by x coordinate
		 How can we do this efficiently? -- linear-time median
	Recur on each of two halves	
	Merge the two upper hulls with the inner loop of Graham's Scan.

	Analysis
		Recurrence equation? -- T(n) = 2T(n/2) + O(n)
		Solution? -- O(n log n)

Lower bounds
	Omega(n) -- Why? -- Must look at all points

	Omega(h log h) -- Why? -- Sorts points on hull

	Omega(n log h)

Other algorithms
	Several optimal algorithms, including

	Chan (1995)
		Includes a combination of Jarvis & Graham ideas

	Kirkpatrick & Seidel (1986)
		 A variation on divide-and-conquer which does some
		 of the merging early to reduce the number of
		 points recurred on.

Beyond 2D
	Giftwrapping and divide-and-conquer most easily generalize to 3D.

	3D is no harder than 2D: Theta(n log h)

	Interestingly, 4+D does seem to be harder:
	Chazelle (1985):
		O(n log n + n^(floor(k/2)))
		Optimal, but not output-sensitive
	Chan (1995):
		O(n log f), for k=2,3
		O(n log f + (nf)^(1 - 1/(floor(k/2)+1)) log^(O(1)) n), for k>3

                f = #faces of hull = O(n^floor(k/2))