Xavier Holt edited http_www_cs_wustl_edu__.md  about 8 years ago

Commit id: 8d1461aa207275579dc420b2995b00f12f5814bb

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.