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
That can't be right, because (among other things), convex hull spits out its points sorted by both the X & Y axes, & hence can be used for sorting. If convex hull could be done in linear time, then so could sorting. At 04:14 PM 8/13/2013, Steve Witham wrote: 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).
participants (2)
-
Henry Baker -
Steve Witham