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.

这里提出的研究是一个正在进行的项目考虑几何问题的启发式方法的延续。我们特别研究了形状和模式匹配以及几何优化问题的方法，例如几何对象的面积高效堆叠和包装。一方面，我们计划开发这些方法，实施它们，并通过实验确定它们的性能。然而，另一方面，我们研究的一个主要目标是从理论上分析这些启发式和已经存在的启发式，以便能够解释它们的性能。该分析的一部分是考虑和描述算法工作良好的实际输入，尽管可能存在构造示例，其中它们显示出低效的最差情况性能。