Geometry Boost List: [ggl] Convex hull complexity ?

Subject: [ggl] Convex hull complexity ?
From: Barend Gehrels (barend)
Date: 2011-07-20 19:44:24

> 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 ?

Sorry, this is a copy-and-paste error. We use the Graham Scan, and it is 
n*log(n).

While I've worked quite some time on the documentation, it was hard to 
get everything right, without postponing the release again and again, so 
there will be some more things incomplete and (hopefully not too much) 
erroneous. In coming version or versions this will be enhanced.

Thanks for the catch.

Regards, Barend