Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards

DOI10.1016/J.COMGEO.2019.101589zbMATH Open1437.51018arXiv1708.05469OpenAlexW2981472776MaRDI QIDQ2173452FDOQ2173452

G. Viglietta

Publication date: 22 April 2020

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: 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 ${\displaystyle }$leftlfloor frac{r-g}{2} ight floor +1${\displaystyle }$ 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 ${\displaystyle }$leftlfloor frac{m-4}{8} ight floor +g${\displaystyle }$ reflex edge guards are sufficient, whereas the previous best known bound was $lfloor11m/72+g/6floor-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(nlogn)$ time.

Full work available at URL: https://arxiv.org/abs/1708.05469

zbMATH Keywords

art gallery problem2-reflex orthogonal polyhedronedge-guarding

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On guarding the vertices of rectilinear domains
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• Triangulating a simple polygon in linear time
• A combinatorial theorem in plane geometry
• Guarding polyhedral terrains
• The art gallery problem is ∃ ℝ-complete
• Face-guarding polyhedra

Cited In (3)

• Edge guards for polyhedra in three-space
• Title not available (Why is that?)
• Minimizing visible edges in polyhedra

This page was built for publication: Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2173452)