In my previous post I proved three out of the four properties of orthogons I originally stated. Now let’s prove the final property:

Every sequence of an even number of X’s and V’s, with exactly four more X’s than V’s, corresponds to the vertex sequence of some orthogonal polygon.

From the previous properties we know that any orthogon gives rise to such a vertex sequence; but how do we know the correspondence goes two ways? Could there be some vertex sequence that for some reason is not possible to realize geometrically?

Of course the answer is no—and here’s one proof. (There may well be better ones; I welcome your ideas! Commenter Gesh also gave a similar proof in the comments to my last post.) The proof is by induction on the number of V’s in the sequence.

First, if the sequence contains no occurrences of V, then it must be XXXX (since there are four more X’s than V’s), and we know this is the vertex sequence of a square.

So now suppose there is at least one V (and hence at least five X’s). There must be an occurrence of either VX or XV somewhere in the sequence. If we delete a VX or XV from the sequence, the resulting sequence still has four more X’s than V’s, and has one fewer V, so the induction hypothesis tells us that it is the vertex sequence of some orthogon. We can take this orthogon and turn it into an orthogon corresponding to the original sequence with the VX or XV re-inserted, by inserting a “step” into the appropriate edge, like so:

Since an orthogon is finite and all its edges must have some positive length, it is always possible to make this “step” small enough that it does not cause any problems with the rest of the orthogon. (For example, there might be another parallel edge very near to the edge in which we are inserting the step; we have to make the step small enough so that it does not intersect with this other edge.) Concretely, we could, for example, make the first step have height , the second one , and so on, with the th step having height .

This proof not only shows that there must exist an orthogon corresponding to each valid vertex sequence, it actually gives an algorithm for constructing one. (There is only a small problem: the resulting drawings look terrible! But one thing at a time…)

As a concrete example, let’s consider the string XXXXXXVVXV.

• Let’s remove the first XV, resulting in XXXXXVXV. We have to recursively produce a drawing of this orthogon before we can re-insert the XV.
  • We remove another XV, leaving XXXXXV.

    • Finally we remove the last XV, leaving XXXX. This is the base case, and corresponds to a square:

      

    • We re-insert XV to give XXXXXV. This corresponds to inserting a step into one of the edges; we’ll make it unit tall, like so:

      

  • Re-inserting XV again yields XXXXXVXV, which corresponds to adding a step (of size ) to the edge just before the convex vertex of the previously added step:

    

• Finally, to re-insert the final XV, we add a size- step in the middle of the step we just added:

  

So, in summary, We now know there is a 1-1 correspondence between orthogons and sequences of V’s and X’s with four more X’s than V’s (where we also consider two sequences equivalent if one is a cyclic rotation of the other, or if one is the reverse of the other.) If we can find a way to enumerate such sequences, we can use them to generate all possible orthogons. I’ll talk about generating these sequences in an upcoming post. Also, as I mentioned before, although this algorithm proves that a drawing always exists for any suitable sequence of X’s and V’s, drawings actually produced with this algorithm do not look very good! The exponentially decreasing steps guarantee nothing will ever intersect, but after inserting five or six of them they basically get too small to see. Producing good-looking drawings turns out to be a very interesting challenge, which I will explain in another post.