Re: [math-fun] convex hull

From: Warren D Smith <warren.wds@gmail.com>

convex hull of N points in 2D (or in 3D) can be computed in O(NlogN) steps and that is best possible in certain models of computation (e.g. algebraic decision tree model).

In 2D at least, there's a linear-time algorithm that works something like the linear-time median... According to the Cormen, Leiserson, Rivest & Stein _Algorithms_ book (the fat one with the mobile on the cover). --Steve