For this topic, I prefer to draw on the board, rather than use Powerpoint.


Problem definition & big picture
	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?

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

	Constant-time "real-world" algorithm:
		Surround points with rubber band and let go.

	I've grouped with sorting, because it is conceptually related, as
	we'll see.

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

		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.

	Aside: How to compute angles?
		Trig functions are expensive.
		Can optimize by using cross-products.  See textbook.
		

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

	Technically, I'll present Andrew's Monotone Chain Algorithm (1979),
	a variation not in the textbook.

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

	Basic idea
		Starting from the right side of upper hull, want to keep making
		left-hand turns.  If we identify a right-hand turn, then the
		point at the turn is not on the hull.

	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 -- Definitely on hull
	Choose point with next smaller x value -- Candidate for next hull point
	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 * time per point)

		O(n log n + n^2) -- Simple analysis of loops

		O(n log n + n) -- Each point can be considered once as left turn
				  and once as right turn

		Illustrate with example, labeling vertices with assigned cost.

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 by x coordinates & 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
	Well-studied, lots of algorithms & variations.

	Several optimal algorithms, including

	QuickHull (1977)
		Similar divide-and-conquer, but partition split can be unbalanced,
		so only optimal in average case

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

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

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 (k dimensions):
	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))