Parallel algorithms in computational geometry with an emphasis on pattern recognition

提出的研究是我们当前在计算几何中的并行算法项目的延续。我们的研究重点是在形状比较和几何模式识别领域。我们计划进一步扩展我们在形状匹配并行算法方面的工作。一方面，对于平面上的形状，除了通过平移匹配外，我们计划考虑更多自由度的变换。特别地，这些包括刚性运动，相似性，或任意仿射变换。另一方面，除了由平面上的曲线组成的形状外，我们还将考虑三维的曲面。更一般的变换和更高维度的匹配导致了计算几何中更多必须解决的一般问题。其中包括高维排列的计算和高维点集的聚类。此外，我们计划为形状匹配的其他启发式技术（如主成分分析或更高矩的使用）开发并行算法。项目的重要部分是实现在现有硬件（多核计算机、GPGPU图形协处理器）上开发的算法。

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).