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.

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