The rules for the exam project are the same as for the previous part.

Part 2 of the exam project has the subtitle "My favorite problem in computational geometry". The intention is that you should be allowed to choose your own problem. This could be an implementation of one of the algorithms in the textbook, one of the algorithms we have considered in the exercises, some other problem from the literature, or even one of your own ideas. The project must be at a reasonable level and have a certain minimum size (more challenging than part 1), so before you start you must consult the lecturer to have your project idea approved.

The entire group (of up to two students) must see the lecturer at the same time for approval of the project idea, programming language, etc. Just send an email with the time slots where you are occupied in the following days, and we will find a time for a zoom meeting for that discussion. There is no deadline for doing this, but since you cannot start your project before this time, you ought to get this done shortly after this announcement; in particular because your initial project idea might not be approved.

Here are possible examples of tasks from what we have covered in the first quarter of the course that could form the basis for this part of the exam project (but talk to the lecturer before you start):

• Example 1: Implement k-d-trees and range trees for arbitrary dimensions. Experiment and try to decide (possibly for a fixed large n) at which dimension the different operations in one of the data structures become faster than the corresponding operations in the other data structure. As a minimum, each structure must have an operation for construction from an unsorted sequence of points, as well as an operation for orthogonal range searching. Textual output should be an option for all dimensions, whereas graphical output only has to work for dimension two. A significant element of this project is the careful comparison and investigation of the properties of the data structures, following the actual implementation.
• Example 2: Implement trapezoidal maps and point location via the accompanying search structure. You may assume that no coordinates have identical x- or y-values. Most will think that this is harder to implement than the work described in Example 1, and a significant element of this project is a careful documentation of the correctness of the implementation.

See the rules below for further requirements.

Hopefully not relevant to anyone, but the faculty has set up plagiarism checks where turned-in solutions are checked up against what can be found on the Internet.

 

---