Computational Geometry Visualization
To the project: GitHub
Contents
About this project
In parallel with the lecture “Grafisch-geometrische Algorithmen”, or, in English, “Computational Geometry” (lecture notes can be found here), I am working through the accompanying book Computational Geometry. To test my understanding, I wanted to try to visualize some of the algorithms covered in the lecture and book. This page is dedicated to said project and contains videos of those algorithms. The source code of the project can be found on GitHub.
Convex Hull
The first problem encountered deals with calculating the convex hull of a given set $P$, which consists of $n$ points in 2D space.
Brute Force approach
As it is better to have a suboptimal algorithm than none at all, the first approach is – as so often – to try and brute force the solution. The algorithm checks for every possible directed edge, whether every other point is to the left of it. If so, the edge is added to a list of convex hull edges $E$. Later on, the convex hull $\mathcal{CH}(P)$ – which is an ordered list of vertices in counter-clockwise direction – extracted from $E$.
This is really slow and takes \(\mathcal{O}(n^3)\) time.
Monotonous Chains
The next algorithm is already substantially faster – see the lecture notes or the book for a detailed explanation. It takes only \(\mathcal{O}(n \log{n})\) time.
Jarvis’ March
The Jarvis’ March algorithm starts from point $p \in \mathcal{CH}(P)$ – e.g., the leftmost point. From there, it brute forces the next point in the convex hull, essentially walking a perimeter around $P$. The runtime of this algorithm depends on the output size and is therefore called an output-sensitive algorithm.
With $k$ vertices in the convex hull, it takes $\mathcal{O}(k \cdot n)$ time.