Project: An Empirical Study of Convex Hull Algorithms
Student Researchers: Ashley Stockdale, Traci Van Patten
Advisor: Dr. Lynn Stauffer
Institution: Sonoma State University




The convex hull is considered a fundamental problem in the field of computational geometry as many other problems are solved by initially computing the convex hull. Our project is exploring the performance of various convex hull algorithms in the plane on a variety of point sets. Although algorithms are known that satisfy the theoretical limits of the problem, their performance on reasonable point sets in comparison to other algorithms is of interest. Our project will examine, implement and analyze the performance of various known algorithms including an untested approach which we called the Extreme algorithm. It is our conjecture that the Extreme algorithm will yield an efficient solution and will compare favorably with the performance of other algorithms in empirical tests. If time allows, our work will extend into larger dimension and into problems that use the convex hull as a fundamental piece in their solution.