Fixed-parameter tractability for geometric optimization problems

许多现实世界中的问题可以表述为几何优化问题。这些是限制于几何设置的组合优化问题，其中目标是最大化或最小化受到由给定的几何输入对象集合引起的大量约束的多个变量的函数。这些问题包括，例如，几何图形，几何包装和覆盖，机器人运动规划和几何图案analysis.We建议系统地研究计算困难（NP-hard）的几何优化问题的参数化复杂性。到目前为止，处理这类问题的主要方法是近似算法。然而，这样的算法往往有过高的运行时间，即使是小的错误大小，而许多几何问题已被证明是不可近似的。另一方面，参数化的复杂性提供了一个框架，一个更精细的，“多维”的分析困难的组合问题。除了传统的输入大小之外，它还根据一个或多个参数来衡量它们的复杂性。在具体的应用中，希望参数取相对较小的值，从而产生实用的（有效的）算法。几何问题通常带有这样的参数，在某种意义上，这些参数测量输入对象的属性。在这个项目中，我们希望开发新的技术，特别是通过结合参数化复杂性和计算几何两个领域的方法，并使用这些技术来解决各个应用领域的具体基本问题，如离散优化，模式分析，传感器网络和艺术画廊。

Many real-world problems can be formulated as geometric optimization problems. These are combinatorial optimization problems restricted to a geometric setting, where the objective is to maximize or minimize a function of a number of variables subject to a large number of constraints induced by a given collection of geometric input objects. These include, for example, problems on geometric graphs, geometric packing and covering, robot motion planning, and geometric pattern analysis.We propose to systematically study the parameterized complexity of computationally hard (NP-hard) geometric optimization problems. So far, the main approach for dealing with such problems has been approximation algorithms. However, such algorithms often have prohibitively high running times even for small error sizes while many geometric problems have been shown to be inapproximable. Parameterized complexity on the other hand provides a framework for a more refined, `multi-dimensional' analysis of hard combinatorial problems. It measures their complexity in terms of one or more parameters in addition to the traditional input size. In concrete applications parameters are hoped to take relatively small values, resulting in practical (efficient) algorithms. Geometric problems often come with such parameters, which, in a sense, measure properties of the input objects. In this project, we would like to develop new techniques, especially by combining methods from both fields of parameterized complexity and computational geometry, and use these techniques to tackle concrete fundamental problems from various application areas, such as discrete optimization, pattern analysis, sensor networks, and art galleries.