Parallel Convex-Hull solver

Posted on Jan 25, 2013

Based on the definition from Princeton, the convex hull of a set of points is:

  • Formally: It is the smallest convex set containing the points.
  • Informally: It is a rubber band wrapped around the “outside” points.

This application was designed to compare time complexity of convex hull problem in both parallel and sequential algorithms. The convex hull problem is solved based on the Graham’s scan algorithm.


  • Parallelization using OpenMPI in C++
  • Graphical visualization using C++ Graphics library (Linux)

Comparison of execution time for 100, 1000, 10000 and 30000 points for MPI runs with 1 Machine 1 Process , 1 Machine 4 Processes and 2 Machines 8 Processes

Source Code
Graph Library