For this project you will be asked to implement two convex hull algorithms. One of your algorithms should be output sensitive—having a runtime that depends on the number of points h on the final hull. The other algorithm should be worst-case n lg n. Note that Chan's algorithm can count as either algorithm, but not both. You must implement at least two approaches. You may work with one partner on this assignment.

Along with your source code, you should hand in a file named README. These files will be imported automatically via handin97. Your README should include a brief summary of your results for the program, along with any known problems/bugs in your code. Also include instructions on how to compile and run your program.

Once you are satisfied with your programs, hand them in by typing handin35 at the unix prompt. You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them.

Home Page

Last updated: Tuesday, September 22, 2020 at 09:07:44 AM