As we discussed earlier, plane sweep paradigm esentially reduces a problem in two dimension into a series of problems in one dimension. Reduction is done by sorting the points. It turns out, complexity of the sorting phase of the algorithm is critical. That's why I used the fastest known sorting algorithm quicksort whose time complexity is . After sorting the points, Plane Sweep algorithm processes each point exactly once. An amortized argument (given in CS373 lecture notes) shows that processing each point takes only constant time. It takes time to construct a triangulation and convex hull of n sorted points. Hence, overall Plane Sweep algorithm takes .