Parameterized Hardness of Art Gallery Problems

DOI10.4230/LIPICS.ESA.2016.19zbMATH Open1397.68091arXiv1603.08116OpenAlexW4391667035MaRDI QIDQ4606288FDOQ4606288

Édouard Bonnet, Tillmann Miltzow

Publication date: 2 March 2018

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.

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)

Cited In (6)

• On the Parameterized Complexity of Red-Blue Points Separation
• Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
• Guarding monotone art galleries with sliding cameras in linear time
• The parameterized complexity of guarding almost convex polygons
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Title not available (Why is that?)

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)