Monthly Archives: April 2011

Nanoexplanations registered at

I’ve registered this blog with, an aggregator and indexer of blog posts about peer-reviewed research.  Their statement of purpose on their About page is:

Do you like to read about new developments in science and other fields? Are you tired of “science by press release”? is your place. allows readers to easily find blog posts about serious peer-reviewed research, instead of just news reports and press releases. has been active in its current incarnation since 2008, and has over 1,000 blogs registered.  Most of these blogs appear to be in the bi0logical and physical sciences, but anyone who blogs about peer-reviewed research according to their guidelines is eligible to register a blog.  Once registered, a blogger includes a specially-generated citation in the content of a blog post, the feedreader recognizes the citation, and then indexes the blog entry, and also includes it in the overall site feed.

My first post indexed by was Connected Guards in Orthogonal Art Galleries, which just appeared.  The special citation appears at the very end of the post.  You can see how the post appears in my blog’s profile.  I’ve gotten decent traffic from being included in this way, even though my post was not general-audience-friendly, and I think the general idea of the site is fantastic, so I plan to continue participating in the future.

From the feeds for Computer Science/Engineering, and for Mathematics, it appears that there are no active “hard science” mathematical science blogs.  The posts related to theorem-proof culture are from physics or computational biology.  There’s definitely some interesting reading, though.  My current favorite: Sexting as a form of attachment anxiety, by psychiatrist Walter van den Broek. also performs meta-analysis of the participatory blogs.  See, for example, this article on gender disparity among science bloggers (men disproportionately outnumber women, both on the site, and in general).

So here’s a list of questions I don’t know the answer to, and I would like to request comments about it.  There are quite a few excellent blogs in computer science (not just theory) and mathematics, but there doesn’t appear to be the same level of online scientific participation in those fields as there is in chemistry, biology or medicine.  The low participation in is one example of this phenomenon.  Are there practical and cultural reasons for this?  Is the TCS community too small to “need” such social-networking tools?  Does blogging about research-level mathematics inherently require one to talk to a very small group, or to “waste” several paragraphs just defining notation and concepts?  Or are computer scientists and mathematicians behind the times, and in need of learning from the interaction tools used in other scientific disciplines?

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. Continue reading