The Art Gallery Problem is one of the fundamental problems in computational geometry. It’s easy to state, easy to motivate, and “simple” variations of it can be very hard to solve. The problem: given a building, what is the fewest number of guards you need to station in order to guard every part of the building? Mathematically, we abstract this out: the floor plan of the building becomes a polygon, and the goal is to determine what is the fewest number of “guard points” I can place on the boundary or in the interior of the polygon, so that every point in the polygon can be connected via a line segment to the guard point, so the segment lies completely within the interior of the polygon.
More generally, this area of study is sometimes called “visibility problems,” and has found application in everything from computer graphics to robot motion. I recently read a paper by Val Pinciu, Connected Guards in Orthogonal Art Galleries, where he proves the following theorem.
Theorem: Let . An orthogonal polygon with sides can be completely guarded by a set of at most connected guards.
Pinciu’s proof is constructive — he finds an explicit guard set — and his core algorithm is brief enough to discuss in a blog post, so that’s what I’m going to do after the jump.
An orthogonal polygon (aka orthogonal art gallery) is a polygon all of whose edges are axis-parallel — all edges horizontal or vertical. Visibility problems in such polygons often have strictly simpler solutions than do the same problems for general polygons. A set of connected guards is a set of points that guards the polygon (all points of the polygon are visible to at least one guard), and so that the visibility graph of the guard set is connected. (To produce the visibility graph of a set of points, take the points as vertices, and draw an edge between a pair if those two points are visible to each other within the polygon.) Note that this property is stronger than just saying, “Every guard is visible to at least one other guard.” That only ensures that the visibility graph has no isolated vertices; we require that the visibility graph have a single connected component.
Pinciu’s algorithm to find connected guards for orthogonal art galleries is the following.
- Input: orthogonal polygon with sides.
- Find a convex quadrangulation of the polygon. Let be the quadrangulation graph.
- Find a 2-coloring of the quadrangulation graph . Such a 2-coloring exists, because is bipartite.
- The least frequently used color gives us a set of vertices .
- Let .
- Output: The set , which is a connected set of guards for .
I won’t prove this works; from the figures I posted at the top, I hope you can see the algorithm is at least intuitively plausible. Rather, I’d like to say something about the hidden difficulties of the first step of the algorithm: “Find a convex quadrangulation of the polygon.”
Quadrangulating a polygon means drawing line segments between polygon vertices such that (1) all line segments lie in the interior of the polygon, and (2) the edges of the polygon and the line segments together decompose the polygon into a set of four-sided regions. (A related, better-known problem is Polygon Triangulation, where the objective is to decompose the polygon into triangles.) A convex quadrangulation is one where all the four-sided regions are convex.
The fact that a convex quadrangulation of an orthogonal polygon always exists — and can be found efficiently — is nontrivial, and required several papers by multiple authors in the 1980s. (Convex quadrangulations do not always exist for general polygons, so orthogonality is necessary.) The original paper that proved existence of a convex quadrangulation, bears the lovely title, “Traditional Galleries Require Fewer Watchmen” (Kahn, Klawe, Kleitman 1983), and contains the following quote:
In many places in this paper our proofs depend on certain configurations having particular properties which appear to follow obviously from the relevant definitions. However, as is often true in geometrical problems, despite their “obvious truth” it seems to be both time-consuming and tricky to provide rigorous proofs of these assertions.
Joseph O’Rourke reproved the existence of convex quadrilateralization in the chapter on Orthogonal Polygons in his respected book on art gallery theorems. (He bought the book’s copyright back from the publisher and has made it entirely downloadable from here.) A few years after the Klein et al. existence result, Lubiw and, independently, Edelsbrunner, O’Rourke and Welzl, produced an algorithm that explicitly found a quadrangulation of an orthogonal polygon with vertices.
I’ll conclude with a little teaser of why this interests me — and why a guy with nanotech interests has written several computational geometry blog posts at this point. In 2007 or 2008, Jack Lutz told me that he believed the theory of VLSI design had connections to the theory of molecular self-assembly. I’ve kept that in the back of my mind ever since. Computational geometry results from the 1980s about orthogonal polygons have extensive application to chip design and VLSI optimization problems. I’m working on some self-assembly optimization problems right now, and I’m building an intuition for them by reading “old school” computational geometry papers. I’ll talk more specifically about some connections between the comp geom work and my own, but probably not for a while yet. In the meantime, I hope you enjoyed this taste of orthogonal art gallery problems.
Val Pinciu (2003). Connected Guards in Orthogonal Art Galleries ICCSA 2003, Lecture Notes in Computer Science, 2669, 886-893 DOI: 10.1007/3-540-44842-X_90