Parallel algorithms in computational geometry with an emphasis on pattern recognition

• Applicant: Professor Dr. Helmut Alt
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 166649592

The proposed research is a continuation of our current project on parallel algorithms in computational geometry. The emphasis of our research is in the area of shape comparison and geometric pattern recognition. We plan to further extend our work on parallel algorithms for shape matching. On the one hand, for shapes in the plane besides matching by translations we plan to consider transformations with more degrees of freedom. In particular, those include rigid motions, similarities, or arbitrary affine transformations.On the other hand, besides shapes consisting of curves in the plane, we will also consider surfaces in three dimensions. More general transformations and higher dimensional matching lead to more general problems in computational geometry which must be solved. Those include the computation of arrangements in higher dimensions und clustering in higher-dimensional point sets.In addition, we plan to develop parallel algorithms for other rather heuristic techniques of shape matching such as the usage of the principal component analysis or higher moments.A significant part of the project shall be the implementation of the algorithms developed on existing hardware (multicore computers, GPGPU graphical coprocessors).

• DFG Programme: Research Grants