EADS Talk: The Parameterized Hardness of the Art Gallery Problem

Title

The Parameterized Hardness of the Art Gallery Problem

Abstract

Given a simple polygon P on n vertices, two points x,y in P are said to be visible to each other if the line segment between x and y is contained in P. The point guard art gallery problem asks for a minimum set S such that every point in P is visible from a point in S. The vertex guard art gallery problem asks for such a set S subset of the vertices of P. A point in the set S is referred to as a guard. For both variants, we rule out any n^{o(k / \log k)} algorithm, where k := |S| is the number of guards, unless the Exponential Time Hypothesis fails. These lower bounds almost match the n^{O(k)} algorithms that exist for both problems. The paper was recently published at ESA 2016 and can also be found on Arxiv. In the talk I will explain the lower bound for point guards only. (joint work with: Edouard Bonnet)

Biography

Tillmann Miltzow is a postdoc at the Hungarian Academy of Science in Budapest in the Parameterized Complexity group of Dániel Marx.(MTA SZTAKI) He did his phd in Berlin under the supervision of Günter Rote at the department of Computer Science of the Free University of Berlin(FUB). His research interests lie mainly in computational geometry, but he also worked on combinatorial problems in the field of social choice, games in abstract graphs, geometric and abstract counting problems, graph drawing problems, approximation algorithms, combinatorial and algorithmic reconfiguration problems.

Host: Mikkel Thorup