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