Below you'll find a list of topics for possible final projects. You have a lot of freedom in choosing a project and you are encouraged to suggest your own topic based on your thesis research, industry experience, or simply your interest. You may also propose variations on the themes below.
By June 15th 2005, you have to submit a one page proposal for approval by the instructor. The submission date of the final project is August 10th 2005 . (For every day of delay you will be fined 3 points out of 100.) Notice that in addition to submitting the project to Idit Haran you need to fix a meeting for an oral exam with Danny (on the project and the course) during the week following the submission deadline.
Every project should include an implementation with (simple) graphic interface, and accompanying text explaining the solution and the implementation.
Do not undertake huge projects. (As you may have learned during the semester, geometric problems seem simpler than they actually are when it comes to implementation.) In particular you may propose partial solutions to the projects proposed here---the part you plan to solve however should be clearly stated in the brief proposal document. It's better that you'll opt for a smaller project and do it thoroughly including extensive experimentation, careful testing, comparison with other solutions experimentally and theoretically (where applicable).
Good luck!
controlled perturbation for lower envelopes of segments
implementing output-sensitive snap rounding for segments as in the
paper:
snap rounding arrangements of circles
adapting graph algorithms from BOOST to CGAL arrangements
exact arrangements of arcs of great circles on a sphere
controlled perturbation for arrangements of little circles on a sphere