Xavier Holt edited O_n_Merge_We_can__.md  about 8 years ago

Commit id: 69101ae5752bd361f4474d4c4e6fb51566c92e4b

deletions | additions      

       

## \(O(n)\)Merge  We can simply apply the sweep-method found in the lecture. For reference, this method went from took  an arbitrary point-set \(\in \mathbb{R}^2\) ordered by x-coordinate to and found  the convex hull of those points. As argued in class, the hull. The  run-time was comprised of an  \(O(n log n)\) for the sorting component sort  and then an  \(O(n)\) for the march, due to the constant number of times we popped a vertex. sweep.  In our case we have already sorted our points as a pre-processing step. As such, we march simply sweep  on \(H_1 \cup H_2\) in \(O(|H_1| + |H_2\)  and return the edges therein. our merging is complete.