*Convex Hull*

##### Graph Theory Demonstration : Given a set of points, determine which
points lie on the "outer perimeter".

1. Pick the points by clicking on the black rectangle area of the applet
2. Choose which algorithm you want to use, then click on the GO
button.

3. If you choose additional point during calculation will cause the program to
recalculate from beginning.
You may also choose additional points and recalculate the result after
each execution. Or you can click on the CLEAR button to clear the screen and
pick new points at any time.

There are many solutions to the convex hull problem. And I choose to implement
two of them. The purpose is to compare the speed and techniques of each
algorithm in finding the hull.
Quick Hull Algorithm : Recursive solution to split the points and check which
points can be skipped and which points shall be keep checking. Best Case --->
O(n log n)

Bruce Force Algorithm : compare all posiible lines with all other points and
find out is the line on the hull. ---> O(n pow 3)

#### Programmed by Jeff So.

The source.

Send comments to
*soj3990@cs.uleth.ca*
Back to my Home Page