Geometry Boost List: [ggl] Convex hull complexity ?

Subject: [ggl] Convex hull complexity ?
From: V D (zedxz2)
Date: 2011-07-20 15:56:54

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 ?

Thanks,
-V