Xavier Holt edited http_www_cs_wustl_edu__.md  about 8 years ago

Commit id: d38be3b78f0abd570f4ba69ca76eb4b4301ef0f1

deletions | additions      

       

An \(O(n)\) merge-step is not a particularly lofty goal to reach. In class our plane-sweep convex hull was comprised of an \(O(n \log n)\) sort and an \(O(n)\) scan. If we were feeling particularly uninspired we could just sub the scan in considering we've already sorted our points by \(x\) coordinate. We assume our algorithm throws out the points \(\not\in H_1\cup H_2\), i.e those on the interior of the left and right sub-hulls. This would make the algorithm at least somewhat output-sensitive to the number of points on the hull, which motivates its use over the standard plane-sweep.  We think we can do a little better. Recall the rubber band metaphor -- the convex hull of a set of points is the shape defined by stretching a rubber band around those points and letting go. What if we stretch a rubber band around two convex hulls? Intuitively, we're going   If we take the rubber-band metaphor  intuitively if we stretch a rubber bound around two convex hulls and release , we're going to get  If we observe **Fig. 1**, the reason we could not include the edge from the two highest points was that it intersected our convex hull. We observe that in all convex hulls seen so far, the edge we include are exactly the ones that are as high