CS 315: Algorithms Term Project
Beloit College, Fall 1998
Convex Hull Animated Applet
by Kunal Mittal

Click here for a list of stuff that I have published.

My Book Store is available by clicking here.

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.

Constructing a Convex Hull:

Brute Force: Compare each point with each other point. O(n^2).
As computer scientists, we don't even want to consider this algorithm. However, it does form a good basis of comparison and an easy to implement solution (for learning purposes).

The Package Wrapping Algorithm: We use the idea of packing a gift. Take the paper and put it over one end of the gift and then move the paper over the gift. The paper will stretch over any curves or irregular parts of the gift.

  • choose the point with miminum x coordinate
  • choose a base line to measure the first angle from
  • find the next point so that the angle from the first point to this second point is the smallest of all the angles from the first point to any of the remaining points

    repeat with last chosen point !
Though this is quite a simple algorithm to understand, it is not particularly efficient. For each point it will be necessary to calculate angles to all the remaining points. Thus the average number of angle calculations per point is approximately n/2. Therefore the total number of angle calculations will be n*n/2 or 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:

Graham Scan Algorithm

  • construct a simple polygon from the set of points
  • take the first two points (point1 and point2) to give line line1-2
  • take the next point (point3) to give line line2-3
  • if angle between line1-2 and line2-3 (the angle at point 2) is < 180 degrees keep these two lines
  • take the line line2-3 and repeat the operations by taking the next point (point4).
  • take the line line3-4 and repeat the operations by taking the next point (point5). Here the angle is >= 180 degrees so remove (line3-4) and (line4-5) and replace with line (line3-5)

    and so on until all the points are covered !!
  • The overall worst cost for Graham's Scan is O(n lg n).

    To Resume Page To my resume
    For more details and email kunal@kunalmittal.com
    @ November 1999 - Kunal Mittal. Copying Prohibited.
    Beloit College