Convex Hull Problem
Divide and Conquer Strategy
In this medium article we will take a look at the convex hull problem and implement a simple divide and conquer algorithm to solve the same.
I have programmed the solution in Python 3 and developed the GUI for the same using Python’s Tkinter library.
What is a Convex Hull?
First things first, a polygon is called a convex polygon if the angle between any of its two adjacent edges is less than 180 degrees.
Given a set of points Q, its convex hull is a convex polygon P such that it encompasses all the points of Q. In simpler words, either the points of Q lie inside the polygon P or on the boundary of it.
Convex Hull Problem deals with the problem of finding convex polygon with the minimum number of edges.
Brute Force Solution
One way to solve the problem would be to join two points at a time and then check if the other points are on the same side or not. For n points, there are n*(n-1)/2 such lines and for each line, there are remaining n-2 points which need to be checked. Thus this brute approach will take O(n³) time.
Divide and Conquer Solution
In the Divide and Conquer Solution, the first thing we need to do is sort the points on the basis of their X-coordinates. This should take O(n log n) time.
We will maintain a solution set where in we will store the lines of the convex hull.
After the sorting, we take the leftmost point A and the rightmost point B. These points are guaranteed to be the vertices of the convex hull. Thus we add the line AB and line BA to the solution set. Down the article I will further elaborate on why I’m explicitly adding line BA to the solution set as well.
Following this we subdivide the points into two groups — points which are to the right of AB and points which are to the left of AB. By doing so we have subdivided the problem into two sub problems.
For the points to the right of AB, we find out the point which is farthest away from the line AB. Let us call this point C.
Using point C, we further subdivide these set of points into three halves X0, X1, X2.
X1 is the set of points to the right of AC and X2 is the set of points to the right of CB. The other points in X0 are the points which are to the left of AC and CB. The set of points in X0 cannot be the part of our solution, so we don’t analyse these points any further.
Thus we have broken down the solution into set of points X1 and X2 for lines AC and CB respectively. In the solution set we replace AB by the lines AC and CB.
Thus we keep dividing the problem into smaller and smaller sub-problems until we find lines which do not have any points to the right of it. These lines are a part of our solution set.
We follow a similar procedure for the points on the left of AB.
For a line AB, the direction of the line is from point A to point B. Similarly for line BA, the direction is from point B to point A instead i.e. the exact opposite. So the right side of AB is the same as the left side of BA. We use this property in the algorithm as well.
So evaluating the right side of AB followed by evaluating the left side of AB is the same as evaluating the right side of AB followed by evaluating the right side of BA. This is why I’m adding line BA to the solution set.
Python Program with Tkinter module
Given below is the Python 3 Program for Solving Convex Hull problem using Divide and Conquer. The GUI is made using Tkinter. Use left mouse button to plant the points on the Tkinter Window, and then click the right mouse button to get the Convex Hull. Use the Mouse Wheel button to reset the program.
Here are the output screenshots of the Program.
