Parallel algorithm to 3-D Convex Hull Problem (Bradley Kuszmaul)

  • courseware
  • Algorithms and Complexity
  • Geometric Algorithms
  • C
  • CILK++
  • computational geometry
  • C++
  • convex hull
  • 3D Convex Hull
  • Threading Challenge Contest
  • matrix determinant
  • tetrahedron volume
  • The included code and white paper provides a parallel solution for the 3-D Convex Hull problem, as described in the included problem description text file. Parallelism is achieved using Cilk++. Possible points for the convex hull are found by repeatedly selecting four points from the input set and finding the largest volumes of the formed tetrahedrons (using matrix determinants). An O(n^4) algorithm confirms those points that are actually on the convex hull from the possible points previously found.
    DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

    There are downloads available under the Creative Commons License license. Download Now
    For more complete information about compiler optimizations, see our Optimization Notice.