GPU computational geometry algorithms

Graphics Processing Unit (GPU) is a kind of computer processor originally designed to render 3D graphics for computer games.  It turns out that the kinds of computations that GPUs do can be applied to many other general purpose computing problems, and in some cases GPU algorithms can be vastly faster than traditional CPU algorithms. Computational geometry is a branch of theoretical computer science concerned with algorithms and data structures for geometric objects.

The leading manufacturer of GPUs is NVidia.  OpenCL and CUDA are two popular programming environments for writing GPU code. I have experience with OpenCL but am open to using other languages.

In addition to these low-level languages, there are emerging high-level tools such as PyOpenCLParFunk, and Thrust.

Project: Implement a novel data computational geometry data structure and/or algorithm on the GPU. Measure its performance and confirm that it is faster than comparable CPU implementations.

Some ideas for worthwhile data structures or algorithms:

  1. A doubly connected edge list (DCEL) or comparable structure. This is an important one; many algorithms depend on using a DCEL structure.
  2. Low-dimension linear programming, convex programming, or LP-type programming.
  3. k-dimension convex hulls. 2D and 3D convex hulls have already been done.
  4. Voronoi diagrams.
  5. Binary space partitions.
  6. Range trees.
  7. Quad trees.
  8. Planar graph separators.
  9. Well separated pairs decomposition.
  10. Anything else implemented in CGAL.
  11. Problems on my list of MapReduce topics might apply too.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s