  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), whose
surface is a connected 2-manifold. We study the NP-complete problem of guarding
a non-convex orthogonal polyhedron having reflex edges in just two directions
(as opposed to three, in the general case) by placing the minimum number of
edge guards on reflex edges only.
  We show that $$\left\lfloor \frac{r-g}{2} \right\rfloor +1$$ reflex edge
guards are sufficient, where $r$ is the number of reflex edges and $g$ is the
polyhedron's genus. This bound is tight for $g=0$. We thereby generalize a
classic planar Art Gallery theorem of O'Rourke, which states that the same
upper bound holds for vertex guards in an orthogonal polygon with $r$ reflex
vertices and $g$ holes.
  Then we give a similar upper bound in terms of $m$, the total number of edges
in the polyhedron. We prove that $$\left\lfloor \frac{m-4}{8} \right\rfloor
+g$$ reflex edge guards are sufficient, whereas the previous best known bound
was $\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 are
segments without the endpoints), proving that the same results hold even in
this more challenging case.
  Finally, we show how to compute guard locations matching the above bounds in
$O(n \log n)$ time.

Computational Geometry;Discrete Mathematics