Triangulations

• Delaunay Triangulations
  
  
  • Project (15 ETCS): Implementation of an algorithm for the Delaunay triangulation in 3d. This problem is solvable in polynomial time. However, polynomial and/or randomized algorithms are far from trivial. There are software packages with these algorithms (for example CGAL) that could be a good starting point. Reasonable user interface to manipulate input and output will be a natural part of the project. Implementation as an applet.
    
    Apart from the implementation, students will be required to get get familar with the theoretical background of Delaunay triangulations in 2- and 3d.
    
    Rationale: Proteins can be represented as polygonal chains in 3d. Structural properties of proteins can to some extend be captures by Delaunay triangulations. This project will be the first step toward the verification of this claim.
    
    No knowledge of proteins nor molecular biology is required. Course in computational geometry would be useful but is not a must.
    
    Good, not too difficult, starting point for Delaunay triangulations could be: Joe Barry, Construction of three-dimensional Delaunay triangulations using local transformations, SIAM J. Sci. Comput. 16, 1292-1307 (1995). Earlier version of this paper appeared in Computer Aided Geometric Design 8(2), 123-142 (1991).