Entwurf und Analyse anwendungsbezogener geometrischer Algorithmen

应用相关几何算法的设计与分析

• 批准号: 47980957
• 负责人: Professor Dr. Helmut Alt
• 金额: --
• 依托单位: Arbeitsgruppe Theoretische Informatik
• 依托单位国家: 德国
• 项目类别: Priority Programmes
• 财政年份: 2007
• 资助国家: 德国
• 起止时间: 2006-12-31 至 2013-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/47980957?language=en
• 关键词: Entwurf; und; Analyse; anwendungsbezogener; geometrischer

The research proposed here is a continuation of an ongoing project considering heuristic methods for geometric problems. In particular, we investigate such methods for shape and pattern matching and for geometric optimization problems, such as area-efficient stacking and packing of geometric objects. On the one hand we plan to develop such methods, implement them, and determine their performance experimentally. On the other hand, however, a major objective of our research is to theoretically analyze these heuristics and already existing ones in order to be able to explain their performance. Part of this analysis is the consideration and characterization of realistic inputs for which the algorithms work well although there are possibly constructed examples where they show inefficient worst case performance.

考虑到几何问题的启发式方法，此处提出的研究是一个正在进行的项目的延续。特别是，我们研究了形状和模式匹配的这种方法以及几何优化问题，例如几何对象的面积有效堆叠和包装。一方面，我们计划开发此类方法，实施它们并通过实验确定其性能。但是，另一方面，我们研究的主要目的是理论上分析这些启发式方法，并已经存在，以便能够解释其性能。该分析的一部分是对现实输入的考虑和表征，该算法效果很好，尽管可能有一些构造的示例显示出效率低下的最坏情况性能。