Output-sensitive algorithms are pretty interesting in general. Previous to Chan's algorithm there was the Kirkpatrick-Seidel algorithm (https://en.wikipedia.org

Output-sensitive algorithms are pretty interesting in general. Previous to Chan's algorithm there was the Kirkpatrick-Seidel algorithm (https://en.wikipedia.org/wiki/Kirkpatrick%E2%80%93Seidel_algorithm https://en.wikipedia.org/wiki/Kirkpatrick%E2%80%93Seidel_alg...), which is more complicated but runs in the same time complexity. Their paper also provides a proof of optimality. For interested students, Dave Mount's computational geometry notes (http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf) provides an excellent overview of algorithms used for most things.