Visualizing Chan's Divide and Conquer 3-d Convex Hull Algorithm

Dana Jansens, from Carleton University

For this talk we will not assume a high level of background knowledge. We will briefly introduce the concept of a convex hull, and how to use divide and conquer in algorithmic design. From there, we will use these concepts to examine and understand Timothy Chan's minimalist divide and conquer 3-d convex hull algorithm. We will discuss the algorithm from a theoretic perspective, and use a visualization of the algorithm to aid in understanding its behaviour.

The visualization program to be presented can be found here: http://cg.scs.carleton.ca/~dana/3dhull/