Parallel algorithms in computational geometry with an emphasis on pattern recognition

计算几何中的并行算法，重点是模式识别

• 批准号: 166649592
• 负责人: Professor Dr. Helmut Alt
• 金额: --
• 依托单位: Arbeitsgruppe Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2010
• 资助国家: 德国
• 起止时间: 2009-12-31 至 2015-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/166649592?language=en
• 关键词: Parallel; algorithms; computational; geometry; emphasis

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

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

项目成果

Approximating Smallest Containers for Packing Three-Dimensional Convex Objects

近似包装三维凸面物体的最小容器

• DOI: 10.4230/lipics.isaac.2016.11
• 发表时间: 2016
• 期刊: Int. J. Comput. Geom. Appl.
• 作者: Helmut Alt;Nadja Scharf
• 通讯作者: Nadja Scharf