4 ms·
There's also Chan's algorithm (http://en.wikipedia.org/wiki/Chan%27s_algorithm http://en.wikipedia.org/wiki/Chan%27s_algorithm)
by filereaper 12y ago
There's also Chan's algorithm
(http://en.wikipedia.org/wiki/Chan%27s_algorithm http://en.wikipedia.org/wiki/Chan%27s_algorithm)
- dllu 12y agoOutput-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.