Web
Analytics Made Easy - StatCounter

Convex Hull Algorithms: Divide and Conquer

Before reading this article, I recommend you to visit following two articles. Many concepts and codes are referred from there.

  1. Divide and Conquer Algorithm
  2. Convex Hull Algorithms: Jarvis’s March (Introduction Part)
  3. An efficient way of merging two convex hulls

Introduction

In this article, I talk about computing convex hull using the divide and conquer technique. The divide and conquer algorithm takes $O(n\log n)$ time. As in the usual divide and conquer algorithms, it has three major steps:

  1. Divide: We divide the set of $n$ points into two parts by a vertical line into the left and right halves.
  2. Conquer: We recursively find the convex hull on left and right halves.
  3. Combine or Merge: We combine the left and right convex hull into one convex hull.

Divide and Conquer steps are straightforward. The merge step is a little bit tricky and I have created separate post to explain it.

Algorithm

  1. Before calling the method to compute the convex hull, once and for all, we sort the points by x-coordinate. This step takes $O(n\log n)$ time.
  2. Divide Step: Find the point with median x-coordinate. Since the input points are already sorted by x-coordinate, this step should take constant time. Depending upon your implementation, sometime it may take up to $O(n)$ time.
  3. Conquer Step: Call the procedure recursively on both the halves.
  4. Merge Step: Merge the two convex hulls computed by two recursive calls in the conquer step. The merge procedure should take $O(n)$ time.

Again, I have described the merging procedure on a separate post. The merge procedure given in the implementation is used from that post.

Implementation

The python implementation of the main procedure is given below.

1
2
3
4
5
6
7
def convex_hull(points):
if len(points) == 1:
return points

left_half = convex_hull(points[0: len(points)/2])
right_half = convex_hull(points[len(points)/2:])
return merge(left_half, right_half)

Remember the input points must be pre-sorted by x-coordinates before calling this function.

1
points = sorted(points, key = lambda p: p.x)

The program returns when there is only one point left to compute convex hull. The convex hull of a single point is always the same point. Note: You can return from the function when the size of the points is less than 4. In that case you can use brute force method in constant time to find the convex hull.

Complexity

The divide step and conquer steps require $O(n\log n)$ time. So the recurrence relation for the divide and conquer part is:
$$T(n) = 2T(\frac{n}{2}) + O(n)$$.
Which gives the complexity of $O(n\log n)$. The initial pre-sort requires extra $O(n\log n )$ time. The overall complexity is, therefore, $O(n\log n)$.

References

  1. Mount, D. M. (n.d.). CMSC 754 Computational Geometry. Lecture. Retrieved August 23, 2018, from https://www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdf
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.