Parameterized Complexity of 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.