Algorithms for Computing Convex Hulls in Higher Dimensions

This talk surveys some major milestones in the development of efficient algorithms for finding convex hulls of finite point sets. We will begin with an introduction to some basic terminology for describing convex hulls and their representations as 2D, 3D and higher-dimensional polytopes. I will also outline the applications and theoretical significance of convex hulls, pointing to relevant literature for those interested in further research. We will analyze several simple algorithms in detail, gaining intuition about their design and run-time, followed by a summary of some of the best existing upper bounds on the complexity of convex hull computation. Finally, if time permits, I will present a very interesting method of establishing lower bounds on computational complexity using algebraic decision trees, that employs results from algebraic geometry.