Applying Threading Building Blocks to Solve Convex Hull Problems

I was browsing the examples that are part of the Threading Building Blocks source code download, seeking an example that illustrates how to apply the concurrent_vector component, and my grep executions brought me to the examples/parallel_reduce/convex_hull directory. This directory contains the source code for two programs that apply the QuickHull algorithm to solve convex hull problems.

What's a "convex hull"?

I had never heard of a "convex hull" (aside from one on a boat) before I started looking at this example code, but it's an interesting class of mathematical problem. The Wikipedia convex hull entry provides the figure below, and the following explanation:

Wikipedia convex hull elastic band analogy

For planar objects, i.e., lying in the plane, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given object; when released, it will assume the shape of the required convex hull.

Tim Lambert, lecturer for the School of Computer Science and Engineering at the University of New South Wales (Australia), describes a convex hull as follows: "The convex hull of a set of points is the smallest convex set that includes the points. For a two dimensional finite set the convex hull is a convex polygon." Tim provides a nice Java applet that lets you play with a set of points (move them, add new points, delete points) to visually understand the nature of a two-dimensional convex hull. Try it out!

Solving for a two-dimensional convex hulls

Thinking about this mathematically, how would we proceed to solve for the convex hull? In the 2D case, you could select three points at random, creating a triangle, then you could extend the polygon by adding points that are outside of the triangle, which would then become a quadrilateral, then a 5-sided figure, etc. This sounds fine, but there is a problem: the solution must be a convex figure. Simply adding points to the figure as I described would not guarantee that the final result will be a convex figure. To guarantee a convex result, we'd need to add a check at each step to ensure that the new bounding figure did not have any concave areas; if it does have a concave area, the point that creates the concavity would have to be removed from the current solution.

If you work with Tim Lambert's 2D convex hull demo, you may be able to see what I'm talking about, and what I'm picturing in my head as I invent "Kevin's method for solving convex hull problems." After a bit of searching, I see that my method is somewhat like the algorithm Tim presents on his incremental algorithm page.

To see a visual demonstration of several methods for solving convex hull problems, visit Tim Lambert's Convex Hull Algorithms page. The Wikipedia's Convex hull algorithms page also introduces several algorithms for solving convex hull problems. I don't see my method anywhere on these pages, so it must not be a very efficient method!

The QuickHull algorithm for convex hulls

The Threading Building Blocks convex hull example applies the QuickHull algorithm for solving convex hull problems. Once again, Tim Lambert helps us understand how this method works through his QuickHull algorithm page and applets. Jay Martin Anderson, Professor of Computer Science at Franklin and Marshall College (U.S.), tells us that:

The "QuickHull" algorithm is so named because of its similarity to the QuickSort algorithm. The algorithm is recursive, and, at each step of the algorithm, points are identified which are internal, and therefore never again are needed for the vertices of the convex hull.

Next up: the TBB QuickHull implementation

Now that we understand the problem at hand, we're ready to start looking at some code. In my next post I'll begin exploring the convex_hull_sample program that is provided with the TBB source code download. Subsequently, I'll also look at the convex_hull_bench program, which provides for side-by-side benchmarking between a "TBB unbuffered push_back" version of the QuickHull algorithm and the "TBB buffered" version of the algorithm (which is implemented in convex_hull_sample).

Kevin Farnham
O'Reilly Media
TBB Open Source Community

For more complete information about compiler optimizations, see our Optimization Notice.