Minimizing visible edges in polyhedra (Q6083182): Difference between revisions

The problem of visibility in discrete geometric settings has a long history, probably the most famous of which is the (planar) art gallery problem posed by V. Klee and solved by V. Chvátal in [\textit{V. Chvátal}, J. Comb. Theory, Ser. B 18, 39--41 (1975; Zbl 0278.05028)]. The problem in three dimensions is understandably more complicated, and much of the literature on the question is motivated by problems in computer graphics and vision (a good introduction is available in [\textit{J. O'Rourke}, in: Handbook of discrete and computational geometry. Boca Raton, FL: CRC Press. 467--479 (1997; Zbl 0907.68195)]). The current work provides bounds on the number of visible edges of a connected compact polyhedral 3-manifold with boundary in \(\mathbb R^{3}\), the faces of which are assumed to be planar polygons whose boundary is a connected union of finitely many line segments; in short, generalized polyhedra with planar faces. There are three main theorems. Theorem. Let \(\mathcal P\) be a polyhedron in \(\mathbb R^{3}\). Then every point \(p\in\mathbb R^{3}\) sees at least six edges of \(\mathcal P\), and this bound is tight. It is worth noting that in the context of this theorem, an edge is considered visible from a point even if only one of its defining vertices is visible. Theorem. Let \(\mathcal P\) be a polyhedron in \(\mathbb R^{3}\). Every point in \(\mathcal P\) sees positive portions of at least six distinct edges of \(\mathcal P\); every point in the interior of \(\mathcal P\) sees positive portions of at least three distinct edges of \(\mathcal P\). Both bounds are tight. Here a \textit{positive portion} of an edge is a segment of the edge visible from the point having positive length. Theorem. Let \(\mathcal P\) be a polyhedron in \(\mathbb R^{3}\). If a point \(p\in\mathbb R^{3}\) does not see any vertex of \(\mathcal P\), then it sees positive portions of at least eight distinct edges of \(\mathcal P\). The bound is tight. Examples verifying the tightness of the bounds are included in the article. The arguments build on the work in [\textit{G. Viglietta}, CGT, Comput. Geom. Topol. 2, No. 2, Paper No. 2, 24 p. (2023; Zbl 07779750)] and use graphs obtained from the edge set of the polyhedron projected orthographically onto a sphere centered on the viewpoint. Of particular import are the \textit{Spherical Occlusion Diagrams (SOD)} which have a relatively simple axiomatic structure. Each SOD is a finite non-empty set of arcs of great circles forming a digraph on a sphere satisfying \begin{itemize} \item[(A1)] Each arc is shorter than a great semicircle, and any two arcs are mutually internally disjoint. \item[(A2)] Each arc feeds into another arc at each endpoint (each arc terminates at an interior point of another arc). \item[(A3)] All arcs that feed into the same arc reach it from the same side. \end{itemize}