Challenge: Prove The Cross Stitch Theorem

Cross-stitch uses different coloured threads to form many 'X'-shaped stitches, arranged in an aesthetically pleasing pattern. The stitches are typically sewn on a woven fabric containing holes arranged in a convenient square grid pattern.

Define a contiguous patch of colour in a cross-stitch pattern to be a set of grid squares all stitched in the same colour that is path-connected. That is, any grid square in the set can be reached from any other square in the set by means of a path through other squares in the set, in which any two adjacent squares along the path share a common boundary. For example, in the illustration, the snowman’s nose forms a contiguous patch of orange. His mouth, on the other hand, is formed from three contiguous patches of black.

To ensure neatness of the finished work, cross-stitchers follow a rule for making the individual stitches: the two halves of the stitch must always be completed in the same order. Let us, say, set the rule that the \ half of a stitch is always made before the / half of the stitch.

So stitches like this

are permissible, but not ones like this:

Note that when making half of a stitch, the thread can go either way along the diagonal, so for example, two ways of sewing a whole stitch are

Other ways of forming this stitch could also involve sewing the \ part of the stitch first, then sewing elsewhere on the fabric, returning to form the / part of the stitch later.

The amount of thread required to complete several stitches can vary. Consider this row of cross-stitching:

Taking the grid squares to be one unit wide, if the stitches are fashioned from left-to-right one X at a time (by taking the thread up through the fabric at grid position A1, then down through the fabric at B2, then B1, A2, B1, C2, C1, B2, C1, D2, D1, C2, D1, E2, E1, D2, E1, F2, F1, E2), then the row requires thread of length 5 + 14*sqrt(2).
In practice there will be some extra thread to start with before A1, and some extra thread to finish with after E2, but we will ignore this extra thread for starting and finishing a section of cross-stitch.

If, however, the \ halves of stitches are made first, then the / halves, in the order A1, B2, B1, C2, C1, D2, D1, E2, E1, F2, F1, E2, E1, D2, D1, C2, C1, B2, B1, A2, then the row only requires thread of length 9 + 10*sqrt(2), a saving of 4(sqrt(2) -1) units of thread.

Your challenge is to prove the following cross stitch theorem:

Another way of thinking of this theorem is this: it is possible to cross-stitch a contiguous patch of colour in such a way that when the thread is passed down through the fabric, it always comes up again at an adjacent hole exactly 1 unit away. Note that the thread can’t come back up through the same hole it just went down, otherwise the thread will fall back through the hole and won’t form the stitch properly.

Hence or otherwise,

You get bonus points if your algorithm is realistically implementable by a cross-stitcher in their head (i.e. it doesn't require a great feat of memory to figure out which bit to stitch next).

---

Disclaimers:

If you do cross-stitch yourself, the author refuses to take responsibility if you get all frustrated because you have managed to deviate from your algorithm and used a whole millimetre of thread more than was strictly necessary.

Alternatively, if you have friends or family who like doing cross-stitch and you take it upon yourself to tell them they are doing it all wrong and using far too much thread, then the author takes no responsibility for any family rows or injuries you may suffer from as a result.

---

[Answer coming soon...]

Author's Note

I am not the only one to notice this cross-stitching result. The topic of cross-stitching a region with a minimal amount of thread was also presented by Barbara Ashton and Kevin Dove in a talk Cross Stitching, Graph Theory and a Least Path Problem that they gave at the joint meetings of the AMS and MAA in New Orleans in January 2007.