Geometry Boost List: [ggl] Convex hull complexity ?

Subject: [ggl] Convex hull complexity ?
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-07-20 18:00:24

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 ?  
> 
> Thanks,
> -V

Convex hull of a simple polygon is well known to be linear time because you know what is "inside" and what is "outside" the curve at every point.  There is no such information in the general case and the algorithm for convex hull of a polygon would not be correct in general if the polygon were self intersecting.  Convex hull of a multipolygon should be at least n log n where n is the number of polygons and obviously convex hull of a set of points should also be n log n.  

I hope that helps.  

Regards,
Luke