the blog of Aaron Sterling

# Connected Guards in Orthogonal Art Galleries

Posted on April 3, 2011

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

### Like this:

This entry was posted in Uncategorized and tagged art gallery theorems, computational geometry, orthogonal polygon. Bookmark the permalink.

### 5 Responses to Connected Guards in Orthogonal Art Galleries

1. chazisop

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?

• Aaron Sterling

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.

• Aaron Sterling

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.

• ### About me

Occasionally streetwise researcher of DNA self-assembly and other nonstandard applications of theoretical computer science.

• ### My Twitter feed

• RT @TheHackersNews: Mystery of Duqu Programming Language Solved goo.gl/fb/VGXIZ #Security #THN #news #securitynews #vulnerability 1 year ago
• RT @EFF: Over 8,200 academics are protesting journals with policies against #OpenAccess. And it's effective: eff.org/r.V8m #oa 1 year ago
• RT @csoghoian: 2nd time in 6 months that Windows security update causes my Truecrypt encrypted laptop to develop unrepairable boot failu ... 1 year ago
• @weasel0x00 Ha! You were right about passphrases not being much stronger than passwords. arstechnica.com/business/news/… 1 year ago
• The frontiers of science are in the strangest places. arstechnica.com/science/news/2… 1 year ago
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 25, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9109757542610168, "perplexity_flag": "middle"}