Three-dimensional art galleries

Question

The well-known art gallery problem starts with an "art gallery" (a simple polygon in the plane, not necessarily convex) and asks for the minimum number of "guards" (points on the polygon) required to "observe the whole gallery" (to have the property that for any point in the interior of the polygon, there is a line segment from that point to a "guard" that lies entirely within the polygon). Chvatal showed that if the polygon has $n$ vertices, then $\lfloor n/3\rfloor$ guards are sufficient, and sometimes necessary, to observe the whole gallery.

If you forget about trying to minimize the number of guards, and simply want to place guards so that they see the whole gallery, it is reasonably clear that if you place a guard at each vertex of a simple polygon, they will be able to observe the whole gallery.

• One way to see this is to note that the assertion is clear for triangles, and then to recall (or to convince oneself) that any simple polygon can be triangulated without adding vertices.

• If visualizing an entire triangulation of the polygon is too "global", one can think "locally" as follows. Fix any point $p$ in the gallery interior. Choose a point $q$ on the polygon such that the distance from $p$ to $q$ is minimized. The line segment from $p$ to $q$ lies within the gallery. If $q$ is a vertex, we are done. Otherwise, $q$ is on the interior of an edge. Pick a direction on that edge and move $q$ along the edge in that direction. Eventually, one of two things will happen: (1) the point $q$ becomes a vertex, or (2) there is a first time at which the line segment from $p$ to $q$ intersects the polygon somewhere besides $q$. In case (1) we are done, and in case (2), we can convince ourselves that at the time that this happens, the closest point to $p$ on the intersection of the polygon and the line segment must be a vertex, and we are again done.

Now switch from two dimensions to three so an "art gallery" is now a polyhedron. If you place a guard at each vertex, can they observe the whole gallery?

The answer, in general, is no.

It may not be clear why it is no, but it is relatively clear that the arguments just given do not generalize in any simple way.

• There are polyhedra that cannot be "triangulated" into tetrahedra without adding vertices. A famous example of this is the Schoenhardt polyhedron. (Yet: experimenting with this applet convinced me that the vertices of this polyhedron do see all of its interior.)

• The "given $p$, pick a closest point $q$ on the polyhedron, and then move $q$ in some direction" idea clearly cannot work (at least without judicious choice of direction), because in the case (2) there is no reason for the closest point on the intersection of the line segment from $p$ to $q$ with the polyhedron to be a vertex in the three-dimensional case. It can pretty obviously be on the interior of some edge.

So it's not counterintuitive, to me, that there are polyhedra whose vertices cannot observe their interiors. But I'd like a better mental image of what such a polyhedron can actually "look like." (A better image, for example, than what I get from the picture on the Wikipedia entry for the art gallery problem.)

Can somebody describe a polyhedron, in such a way that it is in some sense "obvious" that its vertices cannot see all of its interior? So that it is possible to form a clear mental picture of what it would look like to be inside such a polyhedron, at a point where you can't see the vertices? (What do you see?)

Answer 1

I've actually printed the example J.M. mentions from my Art Gallery book on a 3D printer. :-)

The interior consists of many nearly cubical cells, each surrounded by beams above, below, left, right, front, back. Each "beam" derives from an indentation. The cells are not closed--there are cracks because the beams just miss one another. If you imagine standing in one of those cubical cells, you cannot see far, and certainly you cannot see a vertex.

Incidentally, it was discovered by William Thurston independently and at about the same time as Raimund Seidel. I agree that T.S. Michael's book is a great source here.

Answer 2

There's a book by T S Michael, How to Guard an Art Gallery. Only one chapter of the book is actually about guarding art galleries, but that chapter has a section on the three-dimensional case and diagrams of the Octoplex and the Megaplex that you might find helpful.

EDIT: If you have access to The College Mathematics Journal, Michael has a paper, Guards, Galleries, Fortresses, and the Octoplex, Vol. 42, No. 3 (May 2011) (pp. 191-200).

EDIT2: Here's the description of the Octoplex from the book (but the picture in the book is worth 1,000 words). Start with a $20\times20\times20$ cube. Remove a rectangular channel 12 units wide and 6 units deep from the center of the front face (the channel runs from the top of the cube to the bottom). Remove an identical channel from the back face. Also make channels in the left and right faces, going from the front of the cube to the back, 6 units wide and 3 units deep. Finally make channels in the top and bottom faces, running left to right, 6 units by 6 units. What's left is the Octoplex: eight $4\times7\times7$ theaters connected to each other and to a central lobby by passageways one unit wide. And the claim is that even if you post a guard at each of the 56 corners there is a small region at the center of the Octoplex that no one is guarding.

EDIT3 by Rahul Narain: Here is a picture of the Octoplex.

Answer 3

I didn't find the Wikipedia image you linked to difficult to understand, so perhaps it would help you if I just explained it a little.

Here's how I see it. Start with a rhombicuboctahedron, which has the same topology as the given figure. We will be manipulating the six of its faces which are axis-aligned squares. Consider the top square face. Clearly, the center of the polyhedron can see all of its vertices. Now take the face and elongate it in the left-right direction. If you stretch it enough, eventually its vertices will get hidden behind the squares on the left and right. A slice through the middle would look like this:

Now you do the same for the bottom face. The rest of the faces get the same treatment, except in the two orthogonal directions. In the end, you've hidden the vertices of all the axis-aligned faces behind each other. And since every vertex of the polyhedron is a vertex of some axis-aligned face, you're done.

---

From the inside, each triple of adjacent axis-aligned faces form three mutually orthogonal rectangles that are blocking each other's vertices. Kind of like this, where one vertex of each rectangle is hidden.

In the real thing, the other vertices will be hidden by other rectangles, but it's hard to depict them all simultaneously without a full 360° panoramic display.