Xavier Holt edited http_www_cs_wustl_edu__.md  about 8 years ago

Commit id: 1eff5405ff6e67c99761b2646b6cd978474e8743

deletions | additions      

       

## \(O(n)\)Merge  An \(O(n)\) merge-step is not a particularly lofty goal to reach. In class our plane-sweep convex hullalgorithm  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.