Connected Guards in Orthogonal Art Galleries

Figures 2 and 3 from Connected Guards in Orthogonal Art Galleries, by Pinciu (click to enlarge)

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 n \geq 6.  An orthogonal polygon with n sides can be completely guarded by a set of at most n/2 -2 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 P_n with n sides.
  • Find a convex quadrangulation of the polygon.  Let Q_n be the quadrangulation graph.
  • Find a 2-coloring of the quadrangulation graph Q_n.  Such a 2-coloring exists, because Q_n is bipartite.
  • The least frequently used color gives us a set of vertices \mathcal{G}'.
  • Let \mathcal{G} = \{ v \in \mathcal{G}' \mid \textrm{deg}(v) \neq 2 \textrm{ in } Q_n \}.
  • Output: The set \mathcal{G}, which is a connected set of guards for P_n.

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 \mathcal{O}(n \log n) algorithm that explicitly found a quadrangulation of an orthogonal polygon with n 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

About these ads

5 responses to “Connected Guards in Orthogonal Art Galleries

  1. I am not sure I understand the improvement. Wikipedia mentions that floor(n/3) are always sufficient. So (n-2)-2 is an improvement just for n={6..11}. Plus, the floor(n/3) result is general. I sure must be wrong here.. but where?

    • Thanks for the comment, chaziop. The \lfloor n/3 \rfloor upper bound is for guards in arbitrary galleries. The “Traditional Galleries Require Fewer Watchmen” paper shows that the strictly lower bound \lfloor n/4 \rfloor suffices for orthogonal polygons. However, if we require that the guard set have some additional structure, then the number may have to increase. For example, say guard g_1 can see g_2 can see g_3, but g_1 and g_3 cannot see each other. If we only care about guarding the polygon, we may be able to delete g_2 from the guard set, because it is on a location that is visible to other guards. If we require that the visibility graph of the guards be connected, though, the presence of g_2 may be necessary.

      It’s not hard to construct an orthogonal polygon with n sides that requires n/2 - 2 guards if the visibility graph of the guard set must be connected. (Figure 1 of Pinciu’s paper presents one such polygon.)

  2. Pingback: Nanoexplanations registered at ResearchBlogging.org | Nanoexplanations

  3. Indranil Banerjee

    Hi, I found the general art-gallery problem , specially in 3-dimension
    (where there seem to be no definitive classical approach for finding
    solutions, complicated by the possible presences of obscure regions) could be studied in the context of a combinatorial optimization problem. Unfortunately I could not find any relevant references on this, specially no meta-heuristic approaches. Since I am not very informed in this domain, could you possible give me some direction, possible let me know if I am asking the wrong questions? I also want to know what type of spacial optimization problems are there in VLSI/molecular assembly domain which can be modelled to this problem. Please suggest me some references.

    • Both the Handbook on Computational Geometry, and the Handbook of Discrete and Computational Geometry, discuss 3D art gallery problems (illumination problems) some, and they provide reference lists. It’s not an area I know much about. If you would like more specific advice I suggest you ask a question at the Theoretical Computer Science question and answer site. Thanks for the comment, and good luck.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s