Parameterized hardness of art gallery problems

DOI10.4230/LIPICS.ESA.2016.19MaRDI QIDQ4606288zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Tillmann Miltzow

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1603.08116

zbMATH Keywords

computational geometryparameterized complexityart gallery problemETH-based lower boundgeometric set cover/hitting set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Given a simple polygon $mathcalP$ on $n$ vertices, two points $x,y$ in $mathcalP$ are said to be visible to each other if the line segment between $x$ and $y$ is contained in $mathcalP$. The Point Guard Art Gallery problem asks for a minimum set $S$ such that every point in $mathcalP$ is visible from a point in $S$. The Vertex Guard Art Gallery problem asks for such a set $S$ subset of the vertices of $mathcalP$. A point in the set $S$ is referred to as a guard. For both variants, we rule out any $f(k)n^{o(k/logk)}$ 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.

Recommendations

• Computational complexity of art gallery problems
• Vertex guarding in weak visibility polygons
• An approximation algorithm for the art gallery problem
• Approximability of guarding weak visibility polygons
• Inapproximability results for guarding polygons and terrains

Cited in

(9)

• The art gallery problem is \(\exists \mathbb{R}\)-complete
• Guarding monotone art galleries with sliding cameras in linear time
• The parameterized complexity of guarding almost convex polygons
• On the parameterized complexity of red-blue points separation
• Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions)
• Parameterized Hardness of Art Gallery Problems
• Parameterized Analysis of Art Gallery and Terrain Guarding
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)
• The Parameterized Complexity of Guarding Almost Convex Polygons.

This page was built for publication: Parameterized hardness of art gallery problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606288)