Streaming Algorithms for Planar Convex Hulls

Martin Farach-Colton, Meng Li, Meng-Tsung Tsai

Many classical algorithms are known for computing the convex hull of a set of $n$ point in ${\mathbb{R}}^2$ using $O(n)$ space. For large point sets, whose size exceeds the size of t…