Switch branches/tags
Nothing to show
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.


Convex Hull Readme
flash application by Christopher Salvarani (chris@cmu.edu)

What does the program do?
The program finds the convex hull of a set of points inputted by the user. It walks through the algorithm showing each step.

How do I run the program?
You run the program by opening the convex.html file. It will load the HTML page which embeds the flash program.

What is the input?
The input is a set of points. The user clicks various spots on the screen to input the points, and then when ready clicks the appropriate buttons on the bottom bar.

How does Chan's algorithm work?
Chan’s algorithm works by guessing h (the number of points on the convex hull) to be m (initial guess of 2 is acceptable), and then dividing the set of points into O(n/m) subsets of O(m) points and computing the convex hull of each of these with an O(nlogn) algorithm (like Graham scan). This takes O(nlogm).
It then uses a variation of Jarvis march (a naïve O(nh) convex hull algorithm) in conjunction with the already computed convex hulls to construct the convex hull. Jarvis march is sped up to O(nlogm) using the pre-computed mini-hulls, which we can search using a variation of binary search. If the value for m guessed was too low (we figure this out when we take m steps and have not returned to the starting vertex), we bail out and try a greater value for m (the square of m) without exceeding n.
Chan’s algorithm has an overall running time of O(nlogh).