GPU computational geometry algorithmsPosted: July 19, 2012
A 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.
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:
- A doubly connected edge list (DCEL) or comparable structure. This is an important one; many algorithms depend on using a DCEL structure.
- Low-dimension linear programming, convex programming, or LP-type programming.
- k-dimension convex hulls. 2D and 3D convex hulls have already been done.
- Voronoi diagrams.
- Binary space partitions.
- Range trees.
- Quad trees.
- Planar graph separators.
- Well separated pairs decomposition.
- Anything else implemented in CGAL.
- Problems on my list of MapReduce topics might apply too.