Many applications require to generate a mesh for the numerical solution. One way of generating meshes from a set of input points is based on a well-known algorithm in computational geometry called Delauney triangulation. The Delaunay triangulation of a point set is a collection of edges satisfying an "empty circle" property: for each edge we can find a circle containing the edge's endpoints but not containing any other points. These diagrams their and their duals (Voronoi diagrams and medial axes)) have been reinvented, given different names, generalized, studied, and applied many times over in many different fields. The Delauney triangulation is a good starting point for mesh generation, but is not ideal from a numerical point of view. The triangulation may contain triangles with small angles, or triangles with greatly varying area. Quality mesh generation attempts to improve a Delauney triangulation of a point set by inserting additional points (so-called Steiner points), such that the resulting mesh satisfies certain quality constraints (e.g. the minimum angle is larger than a user provided lower bound).
This is an example of a quality 2d mesh generated by the program "triangle". The only points given originally were on the "shore" of Lake Superior. The quality meshing algorithm generated triangles which satisfy an angle constraint.
For general back ground on Delauney triangulations, see Geometry in Action by David Eppstein, UC Irvine, and the links given there.
For quality mesh generation see:
Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, RNR Technical Report RNR-94-002, NASA Ames, January,1994.
Jonathan Shewchuk, Triangle, an incremental Delaunay-based 2d mesh generator, School of Computer Science Carnegie Mellon University, 1997.
For parallel mesh generation see:
Paul Plassman, SUMAA3D (Scalable Unstructured Mesh Algorithms and Applications), Argonne National Lab, 1996.
Roy Williams, DIME: Portable Software for Irregular Meshes for Parallel or Sequential Computers, Chapter 10 in Parallel Computing Works, by Fox, Messina, and Williams, Morgan Kauffman, 1994.
To my knowledge (but some more literature research needs to be done here) a parallel implementation of a quality 2d mesh generator based on Delauney has not been done. Williams in DIME has implemented a refinement algorithm (Rivara's algorithm) which improves angles, but which does not have the quality guarantees of Ruppert's algorithm. SUMAA3D solves a more difficult problem, going from a 3d geometry description to a surface mesh and then to a volume mesh.
The project involves implementing Ruppert's algorithm in parallel on a machine and in a programming language of your choice. I am somewhat partial to the T3E, because I might have some use for the code afterwards. The parallel code should be able to handle fairly large point sets, say up to 10,000 - 20,000 points. Graphical output which shows what the algorithm is doing is part of the project. I am not partial to Ruppert's algorithm. One direction this project could take is to come up with a new parallel algorithm, which delivers a similar result.