
Geometry : 
Subject: [ggl] Convex hull complexity ?
From: Barend Gehrels (barend)
Date: 20110720 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 copyandpaste 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
Geometry list run by mateusz at loskot.net