Parameterized Hardness of Art Gallery Problems

Edouard Bonnet (1) , Miltzow Tillmann (2)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 Universiteit Utrecht / Utrecht University [Utrecht]

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 2 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 f (k)n o(k /log k) algorithm, where k := |S | is the number of guards, for any computable function f , unless the Exponential Time Hypothesis fails. These lower bounds almost match the n O (k) algorithms that exist for both problems.

Mots clés: Computational Geometry; Art Gallery; Parameterized Complexity; ETH lower bound; Computational Geometry

Domaines: Informatique [cs]

Edouard Bonnet, Miltzow Tillmann. Parameterized Hardness of Art Gallery Problems. ACM Transactions on Algorithms, 2020, 16, pp.1 - 23. ⟨10.1145/3398684⟩. ⟨hal-03015328⟩