It’s time to say more about PWW #21, in which I exhibited things like this:
Quite a few commenters figured out what was going on, and mentioned several nice (equivalent) ways to think about it. Primarily, the idea is to draw all possible orthogonal polygons, that is, polygons with only right angles, organized by the total number of vertices. (So, for example, the picture above shows all orthogonal polygons with exactly ten vertices.) However, we have to be careful what we mean by the phrase “all possible”: there would be an infinite number of such polygons if we think about things like the precise lengths of edges. So we have to say when two polygons are considered the same, and when they are distinct. My rules are as follows:
- Two polygons are the same if one is the mirror image of the other.
- Two polygons are the same if one can be turned into the other just by changing the length of some of the edges.
So, for example, I will consider these three polygons are all the same:
(It’s easy to see why the first two are the same. Can you see why the other one is the same too?)
I want to explain some of the mathematics behind generating these. In order to get there, I will start by stating some propositions. Can you see why each of these statements is true?
- Every orthogonal polygon has an even number of vertices.
- Orthongal polygons only have two kinds of vertices: “right turns” and “left turns” (let’s suppose we always travel clockwise around the polygon).
- Every (closed, non-self-intersecting) orthogonal polygon has four more right turns than left turns.
- Every sequence of an even number of R’s and L’s, with exactly four more R’s than L’s, corresponds to the vertex sequence of some orthogonal polygon.
The fourth statement may seem trivial but it is worth a bit of thought: how do you know that you can always draw a non-self-intersecting orthogonal polygon for any valid sequence of left and right turns?