Collaborative Research Experience for Women in Undergraduate
Computer Science and Engineering (CREW) 2000-2001
Final Project Report ‹ May 2001

Project Title An Empirical Study of Convex Hull Algorithms

Student Researchers Ashley Stockdale and Traci Van Patten
Faculty Sponsor Dr. Lynn Stauffer, Associate Professor, Computer Science Dept.
Home Institution California State University, Sonoma
Requested Budget $2000.00

Project Description

Computational geometry encompasses the study of inherently geometric problems for which efficient algorithmic solutions are needed. Applications are far-ranging and include problems in computer aided design (CAD) (such as boundary representations of shapes, intersection and union of shapes, and blending of surfaces), graphics (such as hidden surface elimination and simplification of distant objects), medical computation (such as reconstruction of shapes (organs, bones, tumors, etc.) by determining surfaces from a collection of points), and textile layout (such as the minimization of fabric required to cover a given pattern). This project investigated the convex hull problem in two-dimensions. The work explored the empirical behavior of several convex hull algorithms.

Final Project Report

We spent the past year learning, implementing and analyzing convex hull algorithms. We have successfully met our major project goals and plan on continuing into the summer to finish those left incomplete. We made excellent progress on our research but busy schedules and the desire to do our best in producing accurate results has prevented us from having our final results.

After reading about a variety of convex hull algorithms we selected three algorithms with different approaches and efficiency to compare our proposed algorithm to: Extreme Edges (On^3) which compares points to a line; Jarvis March (On^2) which sorts the points and then computes smallest angles; and Grahams Scan (Onlogn) which sorts the points and then determines if obtuse or acute angles are formed. We have completely implemented the Extreme Edges algorithm and generated a set of test cases to use for comparison between the algorithms. We also implemented the Grahams Scan algorithm and the Jarvis' March algorithm, but problems with mathematical computations for both are preventing us from doing an accurate time analysis. To complete our research we will implement the proposed 'Extreme' algorithm devised by Dr. George Ledin, a professor at Sonoma State University.

When analyzing our results we expect to see a correlation between the algorithms actual run time and its big O notation. When implementing each algorithm our understanding of how algorithms were classified using big O notation was reinforced. Our programming skill was also enhanced as we implemented data structures to store the points and support our necessary access requirements and we used a new integrated development environment for our coding. While our results are not quite complete, the subset of results we obtained did reflect the actual times proportional increase to its O time in comparison to other algorithms.

An important goal of our research project was to experience what graduate research was like for students in Computer Science. We believe our experience was similar to research done at the graduate level because of the successes and difficulties we encountered. We experienced the exhilarations of getting accurate results and the lows of needing additional resources and knowledge in areas few have studied. Through gathering and reading the contemporary information in our area of study, we gained greater skill in the important area of surveying and reviewing the work of peers and of computer science professionals. Our original proposal to use existing convex hull algorithm code resulting in the unexpected discovery that few reliable algorithms are implemented and posted for use. This added to the time needed to complete our research since further effort was necessary to implement all the algorithms with the same care and concern for efficiency. Finally, through choosing a research topic, writing a successful proposal, and collecting and processing the results of our study, attempting to produce an honest document that will be useful to others involved in research, we have gained an important skill set that will help us in our graduate level pursuits, and in our careers.

The CREW programs generosity in supporting undergraduate research has been a valuable experience for our team. We know that the skills learned in this program will help us in our chosen fields. While our research is not yet complete there is satisfaction in the process to date. We are going to continue our research over the summer and post the final results to our web page at http://www.geocities.com/convexhullresearch/index.html.