Parameterized Hardness of Art Gallery Problems | Zendy

Édouard Bonnet | Zendy; Tillmann Miltzow | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Parameterized Hardness of Art Gallery Problems

Author(s) -

Édouard Bonnet,

Tillmann Miltzow

Publication year - 2020

Publication title -

acm transactions on algorithms

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.093

H-Index - 57

eISSN - 1549-6333

pISSN - 1549-6325

DOI - 10.1145/3398684

Subject(s) - parameterized complexity , combinatorics , mathematics , polygon (computer graphics) , simple polygon , guard (computer science) , point (geometry) , set (abstract data type) , exponential time hypothesis , upper and lower bounds , discrete mathematics , monotone polygon , computer science , geometry , telecommunications , frame (networking) , mathematical analysis , programming language

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 f(k)no(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 nO(k) algorithms that exist for both problems.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research