Parameterized Complexity of Geometric Problems

几何问题的参数化复杂性

• 批准号: 75015394
• 负责人: Professor Dr. Christian Knauer
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2008
• 资助国家: 德国
• 起止时间: 2007-12-31 至 2020-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/75015394?language=en
• 关键词: Parameterized; Complexity; Geometric; Problems

Computational geometry is a well established sub-area of algorithm research, which deals with problems involving geometric objects. This includes problems on geometric graphs (e.g., traveling salesman problems), geometric packing and covering problems (e.g., VLSI design, or facility location), robot motion planning problems, geometric pattern matching problems, and statistical estimator problems. The application domain of computational geometry is wide, and includes computer graphics, computer vision, image processing, geographical information systems (GIS) and robotics. Computational geometry usually studies the complexity of geometric problems within the framework of classical complexity theory, and many important problems have been classified as being NP-complete or NP-hard. Recently, there has been an increasing interest in developing a theory for the systematic study of algorithms for NP-hard combinatorial problems. Towards this goal, the theory of parameterized complexity has been developed. Based on the fact that real-life problems often come given with one or more parameters (implicit or explicit to their underlying structure) it measures their complexity in terms of such parameters in addition to the problem input size. Parameterized complexity relaxes the notion of tractability by accepting super-polynomialtime algorithms for NP-hard problems, though confining super-polynomiality, caused by the seemingly unavoidable combinatorial explosion , in the parameters. In concrete applications parameters are hoped to take relatively small values, thus, resulting in practical algorithms. Even though there are some initial results investigating the parametrized complexity of geometric problems, the area is currently a rather scattered landscape of problems, techniques, and results. The goal of the project is to initiate a systematic study of the parametrized complexity of geometric problems, and to develop overarching techniques and ideas.

计算几何是算法研究的一个成熟的分支领域，它处理涉及几何对象的问题。这包括几何图形问题（例如，旅行推销员问题），几何包装和覆盖问题（例如，VLSI设计或设施位置），机器人运动规划问题，几何模式匹配问题和统计估计问题。计算几何的应用领域很广泛，包括计算机图形学、计算机视觉、图像处理、地理信息系统（GIS）和机器人技术。计算几何通常在经典复杂性理论的框架内研究几何问题的复杂性，许多重要的问题被归类为np完全或np困难。最近，人们对开发一种理论来系统地研究NP-hard组合问题的算法越来越感兴趣。为了实现这一目标，参数化复杂性理论得到了发展。基于现实生活中的问题通常带有一个或多个参数（对其底层结构隐式或显式）这一事实，除了问题输入大小之外，它还根据这些参数来衡量它们的复杂性。参数化复杂性通过接受np困难问题的超多项式时间算法来放松可处理性的概念，尽管在参数中限制了由看似不可避免的组合爆炸引起的超多项式。在具体应用中，希望参数取相对较小的值，从而得到实用的算法。尽管在研究几何问题的参数化复杂性方面已经有了一些初步的成果，但目前这个领域的问题、技术和结果还是相当分散的。该项目的目标是对几何问题的参数化复杂性进行系统的研究，并开发总体技术和思想。