Sort by (x, y), sweep twice, pop non-left turns using the cross-product orientation test.
| Algorithm | Time | Space |
|---|---|---|
| Monotone chain | O(n log n) | O(n) |
| Graham scan | O(n log n) | O(n) |
| Gift wrapping | O(n·h) | O(n) |
| QuickHull (avg) | O(n log n) | O(n) |
| QuickHull (worst) | O(n²) | O(n) |
| Chan's algorithm | O(n log h) | O(n) |
| orient (1 test) | O(1) | O(1) |