Bonus Assignment: Implementing Convex Hull Algorithms
The main goal of the bonus project is to learn about the peculiarities of implementing geometric algorithms. Furthermore, you may see that there may be differences between theory and practice in terms of performance of the algorithms.
In groups of two or three you will implement two or three algorithms to compute the convex hull of a set of n points in ℝ2, and experimentally evaluate them. In case your group consists of three people, implement (at least) three algorithms. For all algorithms, try to find a “type” of data sets where this algorithm performs better than the other algorithm(s). Finally, write a short, at most two pages, paper/report about your findings.
The algorithms you can choose from are
- Graham Scan (the algorithm that we covered in detail in lecture one),
- Jarvis March,
- Divide and Conquer
or, if you like some additional challenge,
The most important aspect of your implementation is correctness. That is, make sure that your algorithms always produces the correct convex hull, even if the input is degenerate. For example, if there may be three points on a line. Report only the strictly convex vertices (i.e. at which the interior angle is strictly less than π/2), and in clockwise order.
You will likely run in to an additional issue that, in the theory part of the course, we mostly ignore. See for example what happens when all input points are almost on a line. Think about a way to avoid this issue, and state in your paper what you did to tackle it.
The Experimental Setup
Briefly describe how you obtain/create the data sets you can evaluate your algorithms on. Consider at least two different “types” ways of creating data sets. In particular, for each algorithm A, try to find a “type” of data set for which it computes the convex hull faster than the other algorithm(s). If for cannot find such a set for an algorithm A, explain what you tried, and why you think the other algorithm performs better than A on all your data sets.
Make sure to vary the number of points n in the input datasets, and report the running time of the algorithms.
You will write a short, maximum two page, paper that states
- which algorithms you implemented,
- a very short description of the context (i.e. language and environment) in which you implemented your algorithms and your experimental setup,
- how you made sure that your algorithms are guaranteed to be correct,
- your experimental results (in some easy to read way), and
- a very short, one at most paragraph, conclusion with a recommendation on which algorithm to use when.
Make sure it is well written, and has clear exposition of the data sets and the results. Use figures, graphs, plots, etc. when appropriate.
The assessment will be based on your paper/report only (but you may have to provide your code on request). In particular, on
- how you made sure that your algorithms are correct,
- how you evaluated your algorithms (i.e. which data sets did you use/generate), and
- the presentation of your experimental results.
How/When to hand in your report
Hand in your report by email (at f <dot> staals <at> uu <dot> nl) by Fri 24 Jan 2020 23:59 (CET).