Xavier Holt edited http_www_cs_wustl_edu__.md  about 8 years ago

Commit id: 304ee6588cc3b254b08fe0496a2457665d885559

deletions | additions      

       

## \(O(n)\)Merge  An \(O(n)\) merge-step is not a particularly lofty goal to reach. In class our plane-sweep convex hull algorithm was comprised of an \(O(n \log n)\) sort and an \(O(n)\) scan. If we were feeling particularly uninspired we could just sub this scan in considering we've already sorted our points by \(x\) coordinate. We'd probably throw out the points that were not \(\in H_1\cup H_2\), i.e were on the interior of the left and right convex hulls. This would make the algorithm at least somewhat input-sensitive which motivates its use over the standard plane-sweep.