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

拟议的研究是我们当前关于计算几何算法的项目的延续。我们研究的重点是形状比较和几何模式识别领域。我们计划进一步扩展我们在平行算法上进行形状匹配的工作。一方面，除了通过翻译匹配的飞机上的形状，我们计划以更高的自由度来考虑转换。特别是，这些运动包括刚性运动，相似性或任意仿射变换。另一方面，除了由平面中的曲线组成的形状外，我们还将在三个维度上考虑表面。更一般的转换和更高的尺寸匹配导致必须解决的计算几何形状中更一般的问题。 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).

项目成果

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