Fixed-parameter tractability for geometric optimization problems

现实世界中的许多问题都可以表示为几何优化问题。这些是受限于几何设置的组合优化问题，其中目标是最大化或最小化受给定几何输入对象集合所引起的大量约束的多个变量的函数。这些问题包括几何图形、几何包装和覆盖、机器人运动规划和几何图案分析等问题，我们建议系统地研究计算困难(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.