3 ms·
This is pretty awesome. The trade-offs between the two optimized versions of Graham's scan and Jarvis' march are pretty interesting too, based on the number of
by gleenn 12y ago
This is pretty awesome. The trade-offs between the two optimized versions of Graham's scan and Jarvis' march are pretty interesting too, based on the number of points that lie on the hull.
- 1wheel 12y agoThanks! Chan's algorithms is actually able to combine both approaches and runs in n log h. It is a bit trickier though, so I didn't make an interactive for it. http://en.wikipedia.org/wiki/Chan%27s_algorithm http://en.wikipedia.org/wiki/Chan%27s_algorithm