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

The problem of vertex guarding a simple polygon was first studied by Subir K.Ghosh (1987), who presented a polynomial-time $O(\log n)$-approximationalgorithm for placing as few guards as possible at vertices of a simple $n$-gon$P$, such that every point in $P$ is visible to at least one of the guards.Ghosh also conjectured that this problem admits a polynomial-time algorithmwith constant approximation ratio. Due to the centrality of guarding problemsin the field of computational geometry, much effort has been investedthroughout the years in trying to resolve this conjecture. Despite someprogress (surveyed below), the conjecture remains unresolved to date. In thispaper, we confirm the conjecture for the important case of weakly visiblepolygons, by presenting a $(2+\varepsilon)$-approximation algorithm forguarding such a polygon using vertex guards. A simple polygon $P$ is weaklyvisible if it has an edge $e$, such that every point in $P$ is visible fromsome point on $e$. We also present a $(2+\varepsilon)$-approximation algorithmfor guarding a weakly visible polygon $P$, where guards may be placed anywhereon $P$'s boundary (except in the interior of the edge $e$). Finally, we presenta $3c$-approximation algorithm for vertex guarding a polygon $P$ that is weaklyvisible from a chord, given a subset $G$ of $P$'s vertices that guards $P$'sboundary whose size is bounded by $c$ times the size of a minimum such subset.  Our algorithms are based on an in-depth analysis of the geometric propertiesof the regions that remain unguarded after placing guards at the vertices toguard the polygon's boundary. It is plausible that our results will enableBhattacharya et al. to complete their grand attempt to prove the originalconjecture, as their approach is based on partitioning the underlying simplepolygon into a hierarchy of weakly visible polygons.

A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon