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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Let an orthogonal polyhedron be the union of a finite set of boxes in$\mathbb R^3$ (i.e., cuboids with edges parallel to the coordinate axes), whosesurface is a connected 2-manifold. We study the NP-complete problem of guardinga non-convex orthogonal polyhedron having reflex edges in just two directions(as opposed to three, in the general case) by placing the minimum number ofedge guards on reflex edges only.  We show that $$\left\lfloor \frac{r-g}{2} \right\rfloor +1$$ reflex edgeguards are sufficient, where $r$ is the number of reflex edges and $g$ is thepolyhedron's genus. This bound is tight for $g=0$. We thereby generalize aclassic planar Art Gallery theorem of O'Rourke, which states that the sameupper bound holds for vertex guards in an orthogonal polygon with $r$ reflexvertices and $g$ holes.  Then we give a similar upper bound in terms of $m$, the total number of edgesin the polyhedron. We prove that $$\left\lfloor \frac{m-4}{8} \right\rfloor+g$$ reflex edge guards are sufficient, whereas the previous best known boundwas $\lfloor 11m/72+g/6\rfloor-1$ edge guards (not necessarily reflex).  We also consider the setting in which guards are open (i.e., they aresegments without the endpoints), proving that the same results hold even inthis more challenging case.  Finally, we show how to compute guard locations matching the above bounds in$O(n \log n)$ time.

Optimally Guarding 2-Reflex Orthogonal Polyhedra by Reflex Edge Guards