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

Given a simple polygon $\cal P$, in the Art Gallery problem the goal is tofind the minimum number of guards needed to cover the entire $\cal P$, where aguard is a point and can see another point $q$ when $\overline{pq}$ does notcross the edges of $\cal P$.  This paper studies a variant of the Art Gallery problem in which guards arerestricted to lie on a dense grid inside $\cal P$. In the general problem,guards can be anywhere inside or on the boundary of $\cal P$. The generalproblem is called the \emph{point} guarding problem. It was proved that thepoint guarding problem is APX-complete, meaning that we cannot do better than aconstant-factor approximation algorithm unless $P = NP$.  A huge amount of research is committed to the studies of combinatorial andalgorithmic aspects of this problem, and as of this time, we could not find aconstant factor approximation for simple polygons. The last best-knownapproximation factor for point guarding a simple polygon was $\mathcal{O}(\log(|OPT|))$ introduced by E. Bonnet and T. Miltzow in 2020, where $|OPT|$ is thesize of the optimal solution. Here, we propose an algorithm with a constantapproximation factor for the point guarding problem where the location ofguards is restricted to a grid. The running time of the proposed algorithmdepends on the number of cells of the grid. The approximation factor isconstant regardless of the grid we use, the running time could besuper-polynomial if the grid size becomes exponential.

A Constant-Factor Approximation Algorithm for Point Guarding an Art Gallery