Plane Sweep is a very powerful approach for solving problems involving geometric objects in the plane. Best examples for such problems are line segments intersection, finding the contour of the union of rectangles and Voronoi diagrams as discussed in [6], [9] and [2]. In sweeping, an imaginary vertical sweepline passes through the geometrical objects, usually from left to right. As the sweepline moves, problem has been solved for the data to the left of the sweepline, is currently being solved for the data at or near the sweepline and is going to be solved sometime later for the data to right of the sweep-line.
Basically, plane sweep reduces a problem in two dimensional space to a series of problems in one dimensional space. It is very beneficial because to solve a one dimensional problem is much easier. However, in order to achieve such a reduction one needs to sort the objects (points in our case) from left to right. Since the time complexity of the sorting algorithm is critical, I used a slightly modified version of quicksort algorithm discussed in [2]. Modification is due to the relatively bad performance of quicksort for small number of data. For n less than some CUTOFF value insertion sort is called. Experimentally, a good CUTOFF value is specified as 10 in [14]. Here is the pseudo code for the sweepline algorithm:
. Sort points from left to right
. Construct the initial triangle (convex hull) using the first three points
. for i = 4 to n do
Using 
as the starting point
Move counterclockwise on the convex polygon until the tangent points,
inserting the edges between 
and polygon point to the triangulation
Using 
as the starting point
Move clockwise on the convex polygon until the tangent points,
inserting the edges between 
and polygon point to the triangulation
Update the convex hull removing all points visible to 
except
the tangent points and inserting 
between the two tangent points.
endfor