Quickhull Algorithm

This notebook is a piece of a sequence of notebooks that discuss numerical convex hull algorithms. The goal of these algorithms is to take a set of points $P$ and output a set of extreme points $EP$ such that every point in $P$ is contained in $\text{co}(EP)$.

In this notebook we present the Quickhull algorithm.

Introduction

This algorithm was initially introduced by ??. The complexity of the algorithm is similar to that of quicksort in the sense that on average the complexity is $O(n \log n)$ with a worst case of $O(n^2)$, but like quicksort it tends to do quite well. A nice feature of the quickhull algorithm is, that unlike the Graham scan or monotone chain algorithms, it extends naturally to higher dimensions.