English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Art Gallery is a fundamental visibility problem in Computational Geometry.The input consists of a simple polygon P, (possibly infinite) sets G and C ofpoints within P, and an integer k; the task is to decide if at most k guardscan be placed on points in G so that every point in C is visible to at leastone guard. In the classic formulation of Art Gallery, G and C consist of allthe points within P. Other well-known variants restrict G and C to consisteither of all the points on the boundary of P or of all the vertices of P.Recently, three new important discoveries were made: the above mentionedvariants of Art Gallery are all W[1]-hard with respect to k [Bonnet andMiltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm[Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsenet al., SoCG'17]. Building upon the third result, the classic variant and thecase where G consists only of all the points on the boundary of P were bothshown to be \exists R-complete~[Abrahamsen et al., STOC'18]. Even when both Gand C consist only of all the points on the boundary of P, the problem is notknown to be in NP.  Given the first discovery, the following question was posed by Giannopoulos[Lorentz Center Workshop, 2016]: Is Art Gallery FPT with respect to r, thenumber of reflex vertices? We focus on the variant where G and C are all thevertices of P, called Vertex-Vertex Art Gallery. We show that Vertex-Vertex ArtGallery is solvable in time r^{O(r^2)}n^{O(1)}. Our approach also extends toassert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery areboth FPT. We utilize structural properties of "almost convex polygons" topresent a two-stage reduction from Vertex-Vertex Art Gallery to a newconstraint satisfaction problem (whose solution is also provided in this paper)where constraints have arity 2 and involve monotone functions.

The Parameterized Complexity of Guarding Almost Convex Polygons