Geometry Boost List: [ggl] Convex hull complexity ?

Subject: [ggl] Convex hull complexity ?
From: Arash Partow (arash)
Date: 2011-07-20 19:05:09

On 21/07/2011 4:04 AM, V D wrote:
> The documentation promises that the convex_hull(...) algorithm is a linear time algorithm.
>
> At the same time, it is well known that there's an n*log(n) lower bound for this problem even in the simple case of points in 2D -- in other words, no correct algorithm can guarantee a running time asymptotically less than n*log(n) for an arbitrary instance of the convex hull problem.
>
> Seems astonishing that algorithm for a canonical and well understood problem as convex hull would be buggy, or is it simply an error/typo in the documentation ?
>

Its called the Melkman algorithm:
http://en.wikipedia.org/wiki/Convex_hull_algorithms#Simple_polygon