CS 315: Algorithms Term Project
|Aim: Given a set of 'N' random points on the x-y coordinate, find the Convex Hull to these points.
Explanation:The Convex Hull is a subset of the N random points that forms the outer boundary to all other points. ie. all the remaining points are enclosed within this subset of points. It is easy to infer that the convex hull may contain as little as 3 points or as many as N points.
No convex hull is possible if N <= 2.
In simple terms, think of a gift. When you try to wrap the gift, you want to consider its outer boundary or dimensions. The contents become transparent to the problem of wrapping the gift in paper. The Convex Hull for a gift would be points that lie on or form this outer boundary.
A fundamental property of the convex hull is that any line outside the hull, when extended in any direction towards the hull hits it at one of the vertex points. Thus we can also define the convex hull as a subset of points that could be hit by a line moving towards it at any angle from infinity.
Another obvious inference is that the points with the smallest and largest x and y coordinates have to be part of the subset of points that form the convex hull. This is used as the starting point for many sophisticated algorithms.
Observation regarding running time: It is interesting to note that we cannot possibly have a O(n) algorithm to find the convex hull. There is a theorem that says that if we can find the convex hull in linear time, then we can sort in O(n) time, or even perform matrix multiplication in O(n) time. I will not go into the details of this theorem at this point. I agree that comparing Convex Hull algorithms to sorting algorithms is like comparing apples to oranges, but all we are interested in is counting the number of comparisons operations that need to take place in either case. These facts will be clear after we discuss some of the commonly used algorithms for this problem.
My implementation: I implement two algorithms (Brute Force and Quick Hull) in JAVA. The user can choose any number of random points, the algorithm to use and the speed to run the animation. Then on pressing "start" the applet draws the convex hull to the set of points, using the parameters chosen. (Algorithms described in detail later on, on this page). The user can add points or change the speed of execution even when the algorithm is running. (Note: Adding a point during execution, will cause execution to start from the beginning. I cannot figure out a way to dynamically add points). They cannot change the algorithm being executed without resetting the applet by pressing the reset button. Currently, I have 3 options for random points, 20, 50 and 100. They can be used in combination if suppose 150 points were required, one could first set 100 random points and then 50 more. (The points do not get deleted until the reset button is pressed). There are also 3 speeds of execution, 20%, 85% and Just do it.
Brute Force: Compare each point with each other point. O(n^2).
Quick Hull: This is a recursive, divide and conquer algorithm, that runs in O(NlogN) time. We divide the points into two groups based on a "mid" line calculation which is a linear operation. The mid line is added to both groups and the recursion is done on both halves. The base case for recursion is when we have 2 points in a group. This algorithm as one can see in the applet above is fast and efficient even when the points are randomly distributed and "n" is fairly large.
The Graham Scan Algorithm: This algorithm works by first creating a simple polygon and then removing all the unwanted lines:
and so on until all the points are covered !!
The overall worst cost for Graham's Scan is O(n lg n).
|To my resume||
For more details and email firstname.lastname@example.org
|@ November 1999 - Kunal Mittal. Copying Prohibited.