CSC 320  Assignment 1

Due emailed by class 3/1/06:

The Quick-Hull algorithm is a fast way to compute the convex hull of a set 
of points on the plane. 

As its namesake, quick-sort:

* it is recursive.
* each recursive step partitions data into several groups.

The algorithm follows:

Given points in the plane and line segment AB which is a chord of the 
convex hull (IE, it's endpoints are known to be on the convex hull):
 
*Among the given points, find the one which is farthest from AB. Call it C.
  
*The points inside the triangle ABC cannot be on the hull. Put them in set 
s0.

*Put the points which lie outside edge AC in set s1, points outside edge BC 
in set s2 and points outside AB in set s3. 

*Once the partitioning is done, recursively invoke quick-hull on sets s1, 
s2 and s3. Note that it now requires that the point in each set furthest 
from the associated line be made a part of the hull.

This continues until all points have been processed.

The algorithm works fast on random sets of points because a large fraction 
of the points are discarded with each call.
---------------------------------------------------------------------------

You are to write a Java application which, when a button is clicked,
randomly puts N points on the frame, then computes and draws the convex 
hull.  N can be a constant, but should be defined as a constant at the
beginning of the program.

Your program should work for any N. 

Your program should create a vector of points and produce a vector of line
segments which make up the hull.

A report, describing your java program, your classes and methods, why you 
did what you did and what you like the most about the program should be 
written.  It should include your own statements about how it compares to 
the Quick Sort - other than the ones above. Include time complexity.  In 
thinking about time complexity, consider points that are *not* random, but 
which all lie on the circumference of a circle.  You could even run your 
program with that set of points if desired - not required.

(The report is your documentation and an important part of your grade.)