Convex Hull: The Extreme Edge Algorithm

pretty bad: cubic

The extreme edge algorithm us almost as bad as the "extreme point" algorithm in efficiency.  It has cubic order (O(N³)), which means that the algorithm will run 1000 times longer (in time) for ten times as many points.  Nonetheless, these movies show clearly how much thrashing goes on, even in a really inefficient algorithm.

Example:  for each pair of points, which form a potential edge of the convex hull, see if all other points like on the same side of the edge connecting the two points. If they do, then this line is an edge of the convex hull. The algorithm identifies the edges of the convex hull, but it does not either connect them in either a clockwise or counterclockwise order.

Movies

Nine movies: four with eight points, three with sixteen points, and two with thirty-two points. One of the eight-point movies also includes pauses at important events in the algorithm at which a question is posed to the student.

Remember the guidelines for use of these movies.