First things first: from now on, when talking about polygons with only right angles, instead of calling them “orthogonal polygons” I’m going to start calling them “orthogons”, which sounds cool, is much less clunky than “orthogonal polygons”, and doesn’t seem to already be in use.1 This name was recently suggested to me by Mark Dominus (who was the one who got me thinking about orthogons in the first place).
In my previous post, I posed several properties of orthogons and invited you to figure out why they are true. Here are my proofs.
Every orthogon has an even number of vertices.
Since every vertex is a right angle, the edges of an orthogon must alternate between horizontal and vertical. Hence there must be an even number of vertices; otherwise there would be two vertical edges or two horizontal edges meeting at a vertex, which does not make sense.
Orthogons only have two kinds of vertices: “right turns” and “left turns” (let’s suppose we always travel clockwise around the polygon).
Since writing this, I realized that it is probably easier to think of the vertices as either convex (the corner points towards the exterior of the polygon) or concave (the corner points towards the interior). I’ll use the letter X to stand for conveX vertices, and V for concaVe.
This way, we don’t have to worry about whether we traverse the polygon in clockwise or counterclockwise order (and besides, it can be confusing to figure out what “clockwise” vs “counterclockwise” even means when the polygon doubles back on itself a lot, as in the example shown below).
If you switch directions, left turns become right turns and vice versa. But describing vertices as convex or concave is independent of the polygon’s orientation. You can verify for yourself that the orthogon shown above has the vertex sequence , that is, nine concave vertices in a row followed by 13 convex vertices.
In any case, the reason there are only two types of vertices is simple: if you are travelling along an edge and come to a right-angle vertex, there are only two choices: turn 90 degrees to the left, or to the right.
Every (closed, non-self-intersecting) orthogon has four more right turns than left turns.
Again, the way I originally stated this, with left and right turns, is annoying: if you travel around an orthogon in the opposite direction, then it instead has four more left turns than right turns. We can state this in a much nicer way which is independent of direction: an orthgon always has four more convex vertices than concave.
Obviously this is true for a square, the one possible orthogon with four vertices: there are four convex vertices and no concave vertices. We can see that it also holds for the example orthogon shown above, with nine concave vertices and thirteen convex. Intuitively, the reason it is true in general is that every concave vertex is a turn in “the wrong direction” which needs to be “cancelled” by a convex vertex; on top of that, there need to be four convex vertices to make the whole thing “close up”.
Let’s see how to prove this more formally. We start from the fact that if you sum the internal angles of any polygon with vertices, you get (that is, times degrees). When this is just the familiar fact that the angles of a triangle sum to . But then for bigger , we can always cut up an -gon into triangles, and adding up the angles of all the triangles is the same as adding up all the internal angles of the whole polygon.
Now, suppose an orthogon has convex vertices and concave vertices, and hence vertices in total. Convex vertices have an internal angle of , and concave have an internal angle of . Thus,
If we divide both sides by and multiply by , we get
and then a bit of algebraic rearranging yields .
Incidentally, this now gives us another way to see that there must be an even number of vertices: , which is clearly even.
The final property I stated—namely, that every viable sequence of V’s and X’s describes some orthogon—will have to wait for another post. I’ll give you a hint: the best way to prove this is to give an algorithm that takes a sequence of V’s and X’s as input and produces an actual drawing of an orthogon as output. (But for now it doesn’t matter if the drawing is horrible, just whether one exists!)