Weave Anything

Evolve Your Own Basket

2011-12-03T10:07:00.000-08:00

I led an Adventure in Science (AIS) class at NIH on genotypes and phenotypes. The participants got through the first weaving of a closed basket (genotype = undp), but didn't have time to weave the genotypes they had evolved on their own.

A summary of the instructions for weaving twogs together and interpreting the genotypes is here. More on evolving your own genotypes is here. Finish the weaving and discover what phenotype you have evolved!

Corner-cube weaving of a sphere

2011-11-21T08:15:00.000-08:00

Above is a simulation of a corner-cube weaving of a sphere using the truchet tile below.

More corner-cube weaving examples, an icosahedron and a tetrahelix using the same truchet tile:

Corner-cube weaving: a Woven Surface Truss

2011-11-18T08:38:00.000-08:00

Rhombic tessellations, as for example in anyam gila weaving, often create an illusion of stacked cubes. When the surface really does have that stacked-cube texture, as in some of Torolf Sauermann's parametric sculptures, it can be realized by weaving elements that have 90-degree bends; for example, bent strips of sheet metal. The weaving pattern is not that of the challenging, double-layered anyam gila, but simply open triaxial weave. The geometry of the bends closes up the hexagonal openings.

I liken it to a truss because the interwoven bends stiffen the surface against bending, like corrugating sheet metal.

The bends can be preformed on a two-pin jig. The distance between the outside of the pins needs to be slightly wider than the strip. Here, 0.59" for 0.50" x .017" steel strapping.

The stacked cubes pattern implicitly defines a 2-colorable triangulation:

The dual of the triangulation is a bipartite trivalent map:

Starting from any given map, M, a bipartite trivalent map is defined by the map operation bevel, Be(M). That new map describes a woven truss. The corresponding 2-colorable triangulation is given by Mt(M).

The weavers themselves follow along the edges of the medial of the triangulation, Me(Mt(M)), or, identically, Me(Be(M)).

Assembling tensegrities from undip words

2011-10-07T06:27:00.000-07:00

An undip word specifies a step-by-step procedure that reassembles a spherical map from its edge-rhombs (the quadrilateral faces into which the map operation radial, Ra(), would dissect it.) If a map is a triangulation of the sphere, and its dual is hamiltonian, then there is a least one undip word that reassembles the primal map from its edge-rhombs. (In the special case that we obtained the triangulation as the meta, a.k.a. barycentric subdivision, Mt(), of another map, we are guaranteed that the dual is hamiltonian.)

The assembly procedure does not care what we might have drawn on the faces of the edge-rhombs, and, since many structures and machines can be represented as truchet tiles drawn on edge rhombs, an undip word is also a step-by-step guide to the assembly of any such structure or machine.

In the following I'll assume the reader is familiar with the procedure of reading an undip word to weave twogs into baskets as described in Make a Basket from a Word.

Edge-rhombs are topological objects that can be stretched in any way we wish, but it will forestall confusion if we idealize edge-rhombs as the rhombic shape created by joining two equilateral triangles at a common edge, and further assume that an edge of our primal map (the triangulation) forms the longer diagonal. Therefore, an edge of the dual map (a cubic or trivalent map) forms the short diagonal.

TWOGS through the state of play "uun—"

In order to represent the "assembly" of a twog weaving, I have made a set of paper edge-rhombs with the short diagonal marked in each of three colors. In the photographs below, green is the "photon color" and blue and pink are the "energy colors."

An undip word gains a half edge for free at the beginning of the word, and another half edge for free at the end of the word (the last being the other half of the first.) These moves are encoded, not by a letter, but simply by the fact that the word begins and ends. In reassembling edge-rhombs, we show this peculiar opening move by playing just half of an edge-rhomb (i.e., from an edge-rhomb sliced in two along its longer diagonal.)

The first letter is either a u or n, let's say u. That says, "emit a photon to the left, and then build on to the right." The photon edge will not be completed until later when it gets "absorbed." We show the state of incompletion by placing just half an edge-rhomb on the photon side while building on with a full edge-rhomb on the electron side. If our edge-rhombs have been decorated as truchet tiles, we can now physically build everything that is fully drawn at this state of play. All else must wait until more tiles are added or joined.

Below, edge-rhombs decorated as twogs are carried through to the state-of-play uun—.

Suppose the next letter is d. One can visualize how a half a photon rhomb will be added on the left side of the last played rhomb and then joined to another half photon rhomb already in the work.

That's pretty much all there is to reassembling a map from an undip word that codes it.

Below are four tensegrity patterns also taken through to the state of play uun—.

ZIG-ZAG TENSEGRITY through "uun—"

CIRCUIT TENSEGRITY through "uun—"

STAR TENSEGRITY through "uun—"

DIAMOND TENSEGRITY through "uun—"

Tensegrities from Maps

2011-10-05T06:25:00.000-07:00

Anthony Pugh in his book An Introduction to Tensegrity, identifies three categories of tensegrity patterns: diamond (also known as rhombic), zig-zag, and circuit. Lawrence Pendred found one more: star. Tensegrities conforming to these patterns form stable membranes that can generally be curved to any shape. All four are associated with map operations. The table above shows these tensegrity patterns with their truchet tiles (the truchet tiles replace the edge-rhomb associated with each edge in the base map.)

The diamond (or rhombic, see Xi-Qiao Feng et al.) tensegrity pattern is isomorphic to the map operation snub, Sn(). The compression elements, or struts, of the tensegrity structure, correspond to the chiral edge of snub; the remaining non-chiral edges—which, by themselves, could just as well have been generated by the map operation expand, Ex()—correspond to the tension elements, or tendons, of the tensegrity. When the base map is a triangle on the sphere (as shown above,) this map operation yields the famous 3-strut, 9-tendon, T-prism. When the base map is a tetrahedron, this map operation yields the equally well-known 6-strut, 24-tendon, expanded octahedron.

Pendred's star tensegrity pattern is isomorphic to the map operation capra, Ca(). The compression struts of the tensegrity correspond to the chiral edge of capra; the remaining non-chiral edges—which, by themselves, could just as well have been generated by the map operation chamfer, Ch()—correspond to the tendons of the tensegrity. This arrangement is less rigid than the diamond pattern, but sometimes has useable strength.

The situation is a bit messier for the zig-zag and circuit tensegrity patterns. These patterns have elements that crossover each other without actually touching—thus they cannot fully correspond to the result of a map operation. A stratagem is to use truchet tiles to draw these patterns (as in the table above) with narrow tendons overlying wide struts—not to indicate that they pass in front, but rather that they may pass either in front or behind as the curvature of the surface dictates. Such “floating” tendons and struts are non-physical, but the problem of deciding whether tendons or struts pass in front is fully determined in practice by the spatial coordinates of their endpoints. If the surface the tensegrity structure conforms to is sufficiently curved, strut-tendon and strut-strut collisions are avoided.

The zig-zag tensegrity pattern has tendons that align with the edges of truncate, Tr(), (see Yue Li et al.,) while the struts align with an additional chiral edge which, at its midpoint, crosses over a tendon.

The circuit tensegrity pattern has tendons and struts all of which align with the edges of medial, Me(). The struts join in the common tendon vertex only on alternate passes.

Clearly, there exist many more tensegrity patterns since any consistent way to add struts to a tension network has a chance of working like Snelson's bag-of-bars. In particular, it would be interesting to see if the other chiral map operations correspond to tensegrity patterns.

Undip as a sculptural language

2011-09-27T12:01:00.000-07:00

I'm going to talk about a sculptural construction toy I've designed.

This image shows a close-up of some of the pieces used in the toy. As you see, the pieces are all the same shape in three different colors. They are made out of polypropylene plastic about a half millimeter thick. (Actually, I die-cut them out of Office Depot report covers using a homebrew steel-rule die.)

The pieces of the toy interweave, three-at-a-time, to form a Y-shaped structure. This is an unconventional way to put a construction toy together, and learning to make this three-way join is a big part of the learning curve with this toy.

My wife and I had the fun of showing this toy at World Maker Faire New York a couple of weeks ago. Maker Faire is a show of things that people make themselves sponsored by the publisher of Make magazine. At Maker Faire, there are usually a number of tech-art projects, but also lots of crafts and homebrew electronics.

Our booth was in the "Young Makers" tent. The kids in this photo learned how to make the three-way join. From there the same skill can be used repeatedly to add on to what you've already made, and to make baskets in free-play.

Our booth was actually entitled "Make a Basket from a Word," and the ambition was to move on to a more sophisticated kind of play with the older kids and adults.

The "Word" mentioned in our title is written in a made-up language called undip. Undip uses a four-letter alphabet {u, n, d, p}. I'm going to skip over what we were actually teaching at our booth—how a weaver can interpret an undip word to make a basket—here I want to talk about the language itself, which is a language describing sculptural shapes. You'll have to trust me that a weaver could read the undip words in these captions and weave the baskets shown above them.

English is a natural language, so there is no rule you can rely on to tell whether a given sequence of letters really spells a word in English—you just have to know the language.

Undip is an algebraic language. That means the question of whether a given sequence of letters spells a word in undip is settled by whether or not the sequence can be generated by repeatedly applying a set of rewriting rules.

The two rewriting rules for undip are really simple.

The first rule is that we can insert ud or np anywhere we like in an undip word and the result will be another undip word.

In generating the words of an algebraic language, the only acceptable starting point is the empty word. The empty word is really just a blank space, but it is represented, when necessary, by the Greek letter epsilon. The empty word is considered to be a word in undip (and every other algebraic language.) Confronted with the empty word, the weaver weaves nothing.

Part of the appeal of an algebraic language is this Genesis-like origin. This is a glimpse of the modern, bottom-up, combinatorial esthetic of today's mathematics. Sad to say, it is antithetical to the esthetic of the old mathematics that kids are still being taught in school.

In this sequence, we start with the empty word—itself a word in undip—and choose to invoke the first rewriting rule to insert ud as a suffix, thereby generating the undip word ud. Weaving ud makes the little basket shown.

We can now apply the same rewriting rule again, this time we'll choose to insert np as a suffix. The resulting undip word is udnp. Weaving udnp makes the slightly larger basket shown.

The only other rewriting rule in undip is this one: wherever a left-letter (u or d) is next to a right-letter (n or p) they can switch places.

Having generated udnp, we've got an opportunity to invoke the second rewriting rule because d, a left letter, is next to n, a right letter. We choose to switch their places, generating undp. Weaving undp makes a little basket shaped like a tetrahedron. The tetrahedron is the first of the famed platonic solids.

It is interesting that we can describe platonic solids in undip (a few more letters will suffice to describe the cube or the dodecahedron,) but it is even more interesting that less familiar, less symmetrical—but nonetheless sculpturally interesting shapes—are actually more fundamental.

Inserting two more letters, we can make the four shapes above in variety of ways. Exhausting all possibilities, we can generate 70 different undip words that are 6-letters in length. Weaving all 70, we are surprised to discover that between them they only describe these four shapes. Unfamiliar are they not? Yet, from one perspective they are all more fundamental than the cube.

I'll end with photos of some of the young weaving champions at Maker Faire.

This gentleman wove uunddp from the word and dubbed it barrel.

This gentleman wove uundpd from the word and dubbed it light bulb.

After struggling initially, this young lady persevered and mastered undip better than anyone. She wove two 10-letter baskets (the longest words we had brought along.)

Learn undip and mutate your own!

2011-09-26T10:36:00.000-07:00

English is a natural language on a 26-letter alphabet. In theory there could be as many as 26x26 = 676 two-letter words in English. In truth there are only a few: 'is', 'up', 'on', 'it', etc. Many more two-letter combinations are not words in English: 'aa', 'ab', 'ac', etc. The point is, there is no fixed rule to predict whether a given combination of two letters is a word in English, you just have to know the language.

Undip is an algebraic language on a 4-letter alphabet. In theory there could be as many as 4x4 = 16 two-letter words in undip (in fact there are just two: ud and np.) But being an algebraic language means there is a fixed set of rewriting rules (think of them as editor's moves) that can be applied iteratively to generate all the words in undip—and no word that is not in the language.

Push/Pop Rule: The two-letter sequences ud or np can be inserted (pushed) anywhere in an undip word, including at the beginning or the end, and the result will be another undip word. Inversely, anywhere the sequences ud or np are found in an undip word, they can be deleted (popped) and the result will be another undip word.

The empty word—which might best be represented by a blank space, but that would get confusing—is by convention represented by the Greek letter epsilon. The empty word is itself an undip word, and the ultimate starting point for generating the other words of undip.

Below, the empty word (which describes the empty, or null basket) is edited by invoking the push/pop rule to insert ud as a suffix. The resulting undip word, ud, describes a basket associated with the carbon-carbon bonds of acetylene.

Building onto this undip word, we again invoke the push/pop rule, this time inserting np as a suffix. That generates the word udnp, which describes a basket associated with the carbon-carbon bonds in cyclobutadiene.

We now have an occasion to employ the second rewriting rule.

Shuffle Rule: Anywhere in an undip word where a left letter {u or d} is found next to a right letter {n or p} the two letters can be interchanged and the result will be another undip word.

Below is the editor's markup invoking first the push/pop rule to insert np to make udnp, and then the shuffle rule to interchange d and n to make undp. Those edits convert the acetylene basket into a tetrahedral basket associated with the carbon-carbon bonds in tetrahedrane.

The two rules, push/pop and shuffle suffice, but it can be useful to add a third rule which is really a double application of push/pop.

Flip Rule: Anywhere ud (resp. np) occurs in an undip word, it can replaced by np (resp. ud) and the result will be another undip word.

It is reasonable to add this action as a third rule, because, even though we may imagine push/pop to have been invoked twice (once to remove the original string, and once to insert its replacement) only two adjacent letters are affected—just as in the other single-step mutations. Also, this is the only kind of push/pop mutation that is permissible in the case where mutations must be both local and length-preserving.

Pick any undip word, apply these rules a few times, then try weaving the resulting undip word. It is quite possible that no one else has ever made that basket before. Mutate your own!

Seen at World Maker Faire New York

2011-09-21T07:04:00.000-07:00

We had two beautiful days in Queens, New York at the World Maker Faire. Here is some of the activity at the Make a Basket from a Word booth.

Instructions for "Make a Basket from a Word"

2011-09-21T06:24:00.000-07:00

Here are the complete instructions for the toy Make a Basket from a Word as seen at

Make a Basket from a Word

2011-09-17T18:42:00.001-07:00

"Make a Basket from a Word" is a new toy that lets you make a basket from a word in the undip language.

The kit includes 15 weaving pieces in 3 colors, instructions, and some undip words to weave. More undip words are available here for those who want to make more baskets.

The first step is to learn to put three twogs together. Try following the sequence of images above. Remember to keep all the twogs with their rougher side facing you (that makes the ends look like a curled right hand.)

Try your hand on these:

u d
n p
u d u d
u d u d
u d n p
n u p d
n n p p
u u n d d p
u n n p d p
u d u d n p
n u n d p p
n n u p p d
n p u n d p
n p u d u d
n p n u p d
n p u n u d d p
n u n p p u d d
n u u n p d p d
u d n u n p d p
u u n n d d p p
u u n d n d p u p d
u n d u n u p d p d
u n p n u n d d p p
n u u n d p n p d p
n n n p u p p d n p

To make your own undip word, simply insert one undip word (the simplest are ud and np) anywhere inside another undip word. At the beginning or the end is okay too. That will produce a rather spliced-together looking basket. Applying a second rule solves that: any adjacent pair of left-and-right characters (those are: un, up, dn, dp, nu, nd, pu, pd) can shuffle past each other (becoming, respectively: nu, pu, nd, pd, and so on.)

Mutate your own!

Custom-designed twogs

2011-09-02T07:56:00.000-07:00

Twogs are flat shapes that interweave reciprocally to form a three-way structural joint. By reciprocal, I mean that every twog has the same shape, and plays the same role in forming the joint. Twogs are thus a special case of the broader topic of reciprocal structures, also known as nexorades (see O. Baverel, C. Douthe, and J.-F. Caron.)

The design of the planform shape of a twog is fairly arbitrary save for three points at each end. Those are the special points where two or three twogs engage each other. "Points" is not quite accurate. Examining a twogs joint very closely, we can see light coming through a tiny window where they seemed to touch. Where three twogs meet we see a tiny triangular window; where two twogs meet we see an even tinier lenticular window, shaped like the cross-section of a biconvex lens.

In designing a twog we must allow for this non-point-like intersection (which is due to the finite thickness of the material;) but more significantly, we must design a joint that cannot fit together without some out-of-plane bending, or coning, of the normally flat twogs. This forced conical curvature provides a biasing spring-force that holds the joint tightly together. (See Holger Strom's patent disclosure of IQ's for more on this.)

When a structural joint formed by three twogs is carrying its biasing spring-force, it acts as a tensegrity structure reminiscent of a wagon wheel. Radial compressive forces press together all three sides of the central 3-way engagement, which we may call the hub. Meanwhile, the ring of 2-way engagements, what we may call the rim, carry a band of tension around the periphery of the wheel like three links of a chain. (Just as with the links of a chain, the local interactions where two twogs—or chain links—meet are compressive, but the overall effect is to carry a tensile load.)

The shape of the planform at these three precisely located engagement "points" is given a small radius of curvature, but elsewhere the design of the planform of the twog is free. When all the twogs have the same shape, the engagement radius (the distance to the hub) is the same for all three rim engagements. If the structure were to lie flat, the angular separation of the rim engagements, as seen from the hub, would be exactly 120°. To achieve the biasing spring-force needed for a tight joint, the angular separation should be somewhat less: 116° is a good starting point for experimentation with any particular material and size.

It is desirable to specify the planform shape of a twog in a way that facilitates easy customizatio: that's because we might want to shape every twog differently in order to make a smoother basket. One way to do this is to suppose that the basket shape is specified by an arbitrary triangle surface mesh. Cut two neighboring triangles out of the mesh together, and open the "hinge" of their common edge out flat so that they lie together in the euclidean plane. The two flattened triangles together form a quadrilateral in the plane.

The engagement points of one twog lie easily within this two-triangle plot. In particular, the central region of each triangle contains three engagement points belonging to one end of the twog.

The two-triangle (quadrilateral) plot has four corner-points. The basic idea is to express each control point in the design of the planform of the twog as a weighted average (or recipe) of these four corner-points. Changing the four corner-points—as we do when we choose a different pair of neighboring triangles—then automatically yields a new planform. With a little care in choosing the recipes of the control points, the three twogs meeting at any joint will fit together properly, even though their shapes are all different.

The basic trick is to ensure that the engagement points inside any given triangle have recipes dependent only on the corner-points of that triangle. In particular, the hub is located at the centroid of the triangle; and the single rim engagement point associated with each triangle side (only two of these concern any one twog) is given by a set recipe of the two corner-points that are endpoints of that side, and the opposing vertex.

If the twog's planform is drawn on a joined pair of equilateral triangles, the control point recipes can read off the sides of the appropriate equilateral triangle like reading the composition of a ternary phase diagram.

Control points in the transition region (that is, between the two ends of the twog) can use recipes based on all four corner-points in order to avoid an abrupt transition at the middle.

Connectedness and polyhedrality

2011-09-01T15:40:00.000-07:00

An abstract graph is said to be n-connected if, after the removal of any n-1 of its vertices, all of the remaining vertices are still connected. Connectedness is a property inherited by any map that is an embedding of the abstract graph.

Steinitz's theorem establishes that every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, planar 3-connected graphs are also called polyhedral graphs; their maps (their proper embeddings) are called polyhedral maps.

Since any map that is described by an undip word has a cycle containing all of the vertices (i.e., the hamiltonian cycle the word encodes,) removing a single vertex will open the cycle but not disconnect it. To disconnect the cycle we must remove a pair of vertices that are non-adjacent in the cycle. Therefore: all undip-coded maps are at least 2-connected.

We may also see that disconnecting a trivalent map by the removal of three vertices is unremarkable: removing the three neighbors of any given vertex will always suffice for this. Therefore: no undip-coded maps are more than 3-connected.

The case we need to detect is 2-connectedness. For an undip-coded map to be only 2-connected, the removal of some certain pair of vertices non-adjacent in the hamiltonian cycle (such being necessary and sufficient to disconnect the hamiltonian cycle) must suffice to completely disconnect the map. Therefore, all paths between the two (to-be-separated) portions of the hamiltonian cycle must pass through the two (to-be-deleted) vertices.

Petrie words

2011-09-01T05:05:00.000-07:00

A hamiltonian cycle in a map can seem very indirect, so it is surprising that some hamiltonian cycles are straight. That is, they are as straight as possible under the constraints of the map. "As straight as possible" in a 3-regular map means that left turns alternate with right turns. Such a cycle is called a petrie cycle; and, if it visits all the vertices exactly once, it is called a petrie hamiltonian cycle.

The hamiltonian cycle of the tetrahedron may not seem particularly straight, but it is as straight as the map permits: it alternates left and right turns. It is therefore a petrie hamiltonian cycle.

An undip word intrinsically defines a hamiltonian cycle; if the letters alternate in handedness, then it defines a petrie hamiltonian cycle. (The alternation needs to continue when following upon the last letter with the first, but the parity of the number of letters guarantees this.)

Ivanco, Jendrol, and Tkac in Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs, give a clever way to turn any hamiltonian cycle in a trivalent map into a petrie hamiltonian cycle in a related, somewhat larger, trivalent map. Anywhere the hamiltonian cycle makes a "wrong" (i.e., non-petrie) turn, we fix the problem by simply truncating the vertex.

This procedure has an easy interpretation in undip. Each letter in the undip word represents a vertex. To truncate a "wrong-turn" vertex we use the insertion rule to insert an emit/absorb (a.k.a., open/close) episode of the opposite handedness adjacent to the problem vertex, and then we use the shuffle rule to make this episode enclose the problem vertex. That restores the proper alternation of left and right around that vertex.

To take the simplest example, the word

ud

is non-petrie because the second letter has the same handedness as the preceding letter. Employing our strategy, we can insert an emit/absorb episode of the opposite handedness next to the problem letter:

udnp

Then shuffle to enclose the problem letter d:

undp

If we make it a rule that the first letter of a non-petrie word does not need any correcting, then every undip word has a canonical petrie descendant.

Undip words for bipartite baskets

2011-08-30T10:35:00.000-07:00

A bipartite map is a map that admits a two-coloring of the vertices such that no edge connects two vertices of the same color. Bipartite maps have duals that are chess-colorable. The map operations radial, Ra(), ortho, Or(), and bevel, Be(), yield maps that are bipartite when the base map is orientable. Only bevel guarantees that the resultant map is trivalent, that it is hamiltonian if the base map is connected, and that the dual triangulation is eulerian.

The quadrilateral truchet tiles for these map operations can be suitably pre-colored to show that the result is bipartite: in radial, the new vertices can be given the same color; in ortho, the central vertex can be given a different color; in bevel, diagonal pairs of vertices can be given the same color.

Guitter, Kristjansen, and Nielsen in an article on statistical dynamics and 2D quantum gravity, Hamiltonian Cycles on Random Eulerian Triangulations, have, in effect, counted the number of undip words of length 2n that describe bipartite baskets.

The integer sequence of undip words for bipartite baskets, starting {2, 8, 40, 228, 1424... } is cataloged as sequence A116456 in the Online Encyclopedia of Integer Sequences. The sequence for general baskets, starting {2, 10, 70, 588, 5544...} is A005568.

Bipartite undip words include:

synonyms for the theta graph, e.g., ud

synonyms for the digonal prism, e.g., udud

synonyms for the cube, e.g., uunnddpp.

Non-bipartite undip words include:

synonyms for the tetrahedron, e.g., undp

synonyms for cuneane, e.g., uunddupd.

Table of map operations important in weaving

2011-08-29T06:55:00.000-07:00

In this expanded table, map operations are paired side-by-side with their duals.

Is Bevel the Holy Grail of undip basket making?

2011-08-26T10:02:00.000-07:00

The map operation bevel, Be(M), converts any map into a trivalent, highly hamiltonian map. That makes it describable in undip, in fact it guarantees that it has many shape synonyms, and thus offers many options in choosing a working order for making the basket.

What does a map transformed by bevel look like? The surfaces below were all triangle meshes before bevel got its hands on them.

Truchet tiles for the map operations important in basket weaving

2011-08-25T17:13:00.000-07:00

DUAL OPERATIONS

A pair of map operations A() and B() are considered dual to each other if (refer to George W. Hart's page on the Conway Notation for Polyhedra):

A(M)=Du(B(Du(M))

In this chart the dual operations are:

Id() and Du(),

Ra() and Me(),

Ki() and Tr(),

Ko() and Le().

ROTATION PAIRS

Also of interest are pairs of map operations that we will call rotation pairs, i.e., pairs for which:

A(M) = B(Du(M)) and B(M) = A(Du(M))

Rotation pairs in the chart above are:

Ki() and Ko(),

Tr() and Le().

ROTATION SELF-PAIRS

Map operations with four-fold rotational symmetry are in a sense their own rotation pairs. The ones in the chart above are:

radial, Ra();

medial, Me();

expand, Ex().

The map operation dual, Du(M), rotates the edges of the base map by 90 degrees (compare against the identity operation, Id(M).) Because they have four-fold rotational symmetry, the self-paired operations are unaffected by such a rotation in the base map. They produce the same resultant map whether they operate on a given base map or on its dual.

MAP OPERATIONS THAT YIELD BASKETS

Medial, Me(), and expand, Ex() (expand being the same as medial taken twice,) always yield four-regular, chess-colorable maps. Such a map specifies a chiral pair of plain-woven baskets. Rarely do we need to specify the chirality of weave we have in mind, so I use the term loosely and refer to every four-regular, chess-colorable map as a basket.

Every map can be operated on by medial, Me(), and therefore every map specifies a basket. We will call that basket its medial image.

Every four-regular, chess-colorable map is the medial image of some other map and of that map's dual. We will call those other maps its medial bases.

MAP OPERATIONS THAT YIELD TRIVALENT MAPS

In genetic (a.k.a., undip) fabric construction we are interested in trivalent (a.k.a., cubic) maps, which are maps with three edges meeting at every vertex. The map operations in the chart above that always yield trivalent maps are:

truncate, Tr();

leapfrog, Le();

bevel, Be().

MAP OPERATIONS THAT YIELD HAMILTONIAN MAPS

In genetic fabric construction we are also interested in hamiltonian maps, which are maps that possess a closed path that visits every vertex exactly once. In the chart above the map operations that always yield hamiltonian maps are:

expand, Ex();

bevel, Be().

The argument presented in the previous post shows that this is true for Mrs. Stott's expansion operation, Ex(). When seen as a further development of Ex(M), the action of bevel, Be(M), is to split each vertex of Ex(M) into two connected vertices, thus further enlarging the connected ring of vertices that surround the former location of a single vertex in M. In the image below, the former location of a vertex in M is shown by a dotted circle, and nearby portions of a hamiltonian circuit are shown in red.

Bevel's splitting and reconnection of vertices neither interrupts hamiltonian circuits that were in Ex(M), nor creates any new vertices that are not incidentally visited by the corresponding circuit in Be(M). We conclude that the map operation bevel, Be(), also always results in a hamiltonian map.

Maps produced by medial and bevel are actually quite abundantly hamiltonian since they possess a a hamiltonian circuit for every spanning tree in the base map. That allows freedom in choosing a working order for an undip basket.

PLACING TILES

To place truchet tiles, we must first perform Ra(M) or Ki(M) algorithmically to locate the boundaries of the tiles. The difference between Ra() and Ki() is that Ki() includes the original edges of the base map.

Way to go Mrs. Stott

2011-08-25T16:51:00.000-07:00

I mentioned in my presentation at ISAMA last June that the map operation snub, Sn(M), which is Mrs. Stott's expansion operation Ex(M) plus an added chiral edge, makes a diamond-pattern tensegrity from any base map. The bow, the kite frame (X-module tensegrity,) and the classic three-strut tensegrity are inventions that made their separate appearances in human history centuries apart. It is remarkable to see them all fall from Mrs. Stott's expansion operation when applied to the simplest maps.

It occurred to me last night (while relaxing at the Strathmore Ukelele Festival) that I had missed another remarkable property of this map operation: the resultant map is always hamiltonian. In particular, any spanning tree in the base map (it's guaranteed that there is at least one spanning tree in any connected map) specifies a hamiltonian circuit.

To see that this is true, consider a fanciful strategy of walking "around the outside" of a spanning tree of the map M in a counter-clockwise direction. This strategy lets us visit every vertex of the tree in a closed cycle, but at the cost of visiting every edge twice (seeing the edge as an isthmus, we will be traveling along it once on each shore and in opposite directions) and visiting each vertex a number of times equal to its valence in the tree. Mrs. Stott's expansion duplicates edges and vertices just enough (times-two for the edges; times-the-valence for the vertices) to eliminate these duplicated visits. That turns our fanciful trip around a spanning tree in the old map into a guaranteed hamiltonian circuit in the new map.

More on ply-split braiding of baskets

2011-08-24T05:12:00.000-07:00

Mathematically, a plain-woven basket embodies a 4-valent, chess-colorable map. Such a map can be generated from any base map M, by the map operation of taking its medial, Me(M).

A visual way to think about a map operation such as medial is as a quadrilateral truchet tiling. Every edge in a map is associated with a quadrilateral domain of the surface. The union of all of these quadrilateral edge domains is the surface itself. Ironically, the task of drawing an arbitrary map on a surface, which seems so free—a dessin d'enfant—also accomplishes the goal of sudividing the surface into quadrilaterals, a task that might seem workaday and onerous. The map operation kis, Ki(M), makes explicit the boundaries of these quadrilateral edge domains.

A quadrilateral edge domain—save for the edge itself, and a portion of the vertices at each end—is empty. Using the technique of truchet tiles we can replace this empty quadrilateral region with a tile decorated with new vertices and new edges, plus any subset of the old edge and vertices that we wish to keep. For example, a truchet tile for medial leaves out the original edge and both its vertices (for comparison, a truchet tile for the map operation identity, Id(M), reveals the original edge):

If our truchet tiling (and weaving) is not to be arbitrary, our truchet tiles must all be identical, and their placement must be automatic.

In an undirected map (i.e., one where edges are not decorated with arrows,) we discover that we have an option in placing quadrilateral tiles: we can rotate them 180 degrees in the plane, and they still line up with the old edge. In consequence, we will be adding monkey-business to our map (directing an edge) every time we place a tile—unless, of course, the decoration on the tile itself has two-fold rotational symmetry, then our choice will make no substantive difference. (Thus, amazingly, any 2D periodic structure or mechanism that can be expressed as a quadrilateral truchet tile with two-fold rotational symmetry can be applied to any map of an any surface.)

Monkey-business not being what we're looking for, we are limited to weave crossings having two-fold rotational symmetry. The ply-split crossings illustrated in the previous post lack this.

Peter Collingwood's article "Ply-Split Braiding" in Weaver's issue 29 illustrates a twined linking that does have the required symmetry:

But then we'll be back to using bent twongs.

A possibly better option, which is really just ordinary braiding with a twist, is to open out each cord into a 2x2 woven crossing:

Straight twongs: unit ply-split braiding

2011-08-22T09:33:00.000-07:00

Twongs don't have to be bent (it saves some trouble if they aren't.) Both 2-ply and 3-ply twongs can be made without the usual bends if they are to be used in a kagome weave pattern. (This familiar tessellation of hexagons and triangles is the medial of both the regular tessellation of triangles and of the regular tessellation of hexagons.)

The crossings at the vertices are 2-ply over 2-ply and belong to the technique of ply-split braiding.

The ply-split crossings are especially advantageous with twongs because they "lock" and cannot be undone by simple untwisting.

Here is a small sample of 2-ply, unit ply-split or UPS braiding in a kagome weave.

Brawny 3-ply twongs

2011-08-22T09:01:00.000-07:00

An important trade-off in the design of twongs is the length of the overlapped, or 2-ply section. If the 2-ply section is short, the junction is not strong. If it is long (it can be extended to up to 50% of the inter-vertex distance) it creates a concentration of bending stress that prevents the composite member from bending smoothly. The maximum overlap is limited to 50% of the inter-vertex distance because the overlaps from each vertex cannot overrun each other if the construction is to remain 2-ply.

Going to a 3-ply construction, i.e., where the twongs are formed by twisting a triple strand of wire, opens new possibilities.

In a 3-ply construction the overlaps can now be 100% of the inter-vertex distance. That means the inter-vertex distance can be cut in half for the same length of overlap, permitting much brawnier and stronger structures to be built. The structure at the vertex is still single-ply as before, but the overlapping of the overlaps makes for a 3-ply composite structure between vertices.

All baskets are closed

2011-08-22T07:58:00.000-07:00

Baskets lie at the transition between knots and surfaces. Put another way, it is in contemplating baskets that the questions we ask about knots begin to supplant the questions we ask about surfaces. As a case in point, it can seem arbitrary to insist (as is always done in map theory) that a surface be closed, i.e., that it can have no boundary. On the other hand, in knot theory it would be absurd to posit a knot with a boundary.

It may seem intuitive that baskets need not be closed (what earthly use would a closed basket be?) But, in truth all baskets are closed. To see this we have to look more closely at the nature of the selvage, the proper weaving termination of a basket at its mouth.

Here are representations of properly selvaged basket openings of 3, 4, and 6 sides.

They can be tiled together to form a plain (i.e., strictly over-and-under) weaving:

Every plain-woven basket is entirely composed of such properly selvaged openings. There is no other sort of opening or boundary in a properly selvaged basket. In that sense, all baskets are boundary-less and therefore closed.

Swamp backstroke update

2011-08-20T06:13:00.000-07:00

Yesterday I finally found the increment of speed I've been looking for half the summer. The speed key in the high-gear of the swamp backstroke is to bring the inward sweep of your hand very close to your hip. I can think of several reasons why this works, but it does work amazingly. I could feel myself making a bow wave (for the first time ever,) and every so slightly going prow-up like a motorboat.

Pick any or several of these reasons:

the well-known clap-fling effect may help reverse the circulation of the flow around your hand for the return outward sweep,

because flow velocity next to your body can only be straight downstream, forcing the slipstream of your hand against your side converts some of the useless side-to-side momentum of the slipstream to downstream momentum,

by applying your thrust near the widest part of your body, you energize the boundary layer in a way that reduces drag,

keeping the thrust-producing maneuver as inboard as possible reduces drag from the shoulders and arms in making the stroke.

Also, the muscular effort in this position seems easier.

I can only say that the swamp backstroke is already fun and getting faster.

The dream would be to somehow combine this hip-clapping underwater stroke with the underwater dolphin kick to make an underwater backstroke, surfacing only intermittently to spout like a dolphin. I'm not nearly athletic enough to try that.

The Swamp Backstroke: a new swimming stroke with two "gears"

2011-08-18T08:21:00.000-07:00

The swamp backstroke is a stealthy, medium-speed swimming stroke propelled solely by underwater movements of the arms and hands. It is particularly suited to shallow water.

I am certainly not the first person to try this method of swimming—which in essence is simply floating on your back and propelling yourself with sculling motions of your hands—but I am coining the name and publishing these observations in the hope of getting more people interested in developing this useful swimming stroke.

The swamp backstroke, in common with other backstrokes, has two familiar characteristics:

breathing is unimpaired,

you can see everything around you, but not where you are going (extreme caution around pool walls and other swimmers is urged.)

The swamp backstroke stroke also has some characteristics which are unique:

only the arms and hands are used for propulsion,

all movements are underwater,

the body stays flat-level in the water with no rocking,

the hands are used continuously as efficient hydrodynamic lifting foils: drag plays no useful role in this stroke,

water as shallow as a wading pool can be successfully navigated,

there is a "low gear" and a "high gear" in the swamp stroke, that is, the best hand movement at high speed is fundamentally different from the best hand movement at low speed.

Swimming the swamp backstroke I have been able to achieve a top speed of about 1m/sec. That's done without heroic effort (I'm 56 and not an athlete.) A competition-level freestyle sprint would be twice as fast, but the swamp stroke uses much less of the body's musculature and is nearly silent. Because propulsion in the swamp backstroke is hydrodynamically efficient, I hold out hope that there is a speed (somewhere below one meter per second) where the swamp backstroke is the most metabolically efficient way to cover long distances. In shallow water at least, that's likely to be true.

HOW TO DO THE SWAMP BACKSTROKE

This is not a well developed stroke, so will not to try to be specific about my own arm and hand movements, they are probably not optimal anyway. Also, when it comes to rapid underwater movements of the hands, you will find the water has a large say: what you are trying to do isn't exactly what the water makes you do.

BODY POSITION

I will be specific about keeping your body in a trim position. When floating on your back the natural tendency is to raise your head and let your butt hang down an inch or two. You certainly can do a swamp backstroke in this posture, but it will be like dragging a parachute. You must get your butt up to achieve any speed, and this requires letting your head back, ears in the water, and arching your back slightly.

HAND MOVEMENTS: LOW-GEAR

You can find the hand movements for low-gear by standing in deep water and learning the feel of unseparated hydrodynamic flow over your hands. Palms facing down, move your hands back-and-forth from side-to-side at various angles of attack. The force of the water against your palm can be surprisingly strong. Then, suddenly, at too great an angle of attack, the flow stalls (separates) making the flow over the back of your hand feel bubbly and less dense. Efficient propulsion requires staying in the unseparated, unstalled regime. Experiment standing in deep water till you are satisfied you can produce a strong downward thrust while moving your hands near your hips. Fingers fully extended and held tightly together work best.

Now, do the same hand movement while floating on your back, and you're off!

Steering in the swamp backstroke is accomplished by simply exerting less thrust on one side. See what variations make you go faster. Get comfortable swamping in low-gear—and used to anticipating and avoiding obstacles—before trying to learn high-gear.

HAND MOVEMENTS: HIGH-GEAR

The limitation of low-gear is that once you start moving through the water with some speed, the relative direction of the water approaching your hand changes. It soon becomes anatomically impossible to rotate your wrist far enough to stay in the unstalled regime on each sweep of the hand.

Notice that in low-gear the flow over your hand alternates: at alternate times the thumb-side or the pinky-side of your hand forms the leading edge of the airfoil. To achieve higher speed through the water you must transition to a non-alternating flow where the the thumb-side of the hand is always the leading edge. This transition proves easy, but it must be done at speed since the new hand movements would be totally ineffectual, and even nonsensical, in still water.

While swamping at speed, you rotate your hands so that the thumb-side faces the oncoming water. This requires lowering your elbows (which can be a problem in very shallow water.) Keep your hands underwater and place your elbows as deep as possible—that will leave you in a position where your hand is a straight extension of you forearm, the both being inclined about 45 degrees to the water's surface. In that position all pitch rotations of the hand originate at the elbow.

Don't think about what you are going to do, or how it can possibly propel you forward. (As I said, the high-gear movements would be nonsensical in still water.) Concentrate only on doing work against the hydrodynamic lift force on your hands.

Lift is the sideways component of the hydrodynamic force, it is always perpendicular to the direction of the flow, and it is non-dissipative. That means that 100% of the work you do against it goes into increasing the kinetic energy of the flow. In this case, it efficiently moves you forward through the water at a respectable clip.

In my experience, fast, small hand movements near the hips are best. I'll be interested to hear your results.

The Plain Weaving Theorem again: The Vending Machine Algorithm

2011-08-15T11:15:00.000-07:00

I am again writing about the Plain Weaving Theorem that Akleman, Chen, Xing, and Gross demonstrated by a topological proof in 2009. In essence the PWT states that every connected map specifies an enantiomorphic pair of plain-woven baskets. By plain-woven it is meant that every weaving element goes over-and-under in strict alternation—which is not exactly the way the term is commonly understood in the fiber arts. In knot theory terms, a plain-woven basket is an alternating link whose projection is properly embedded in a surface.

A connected map can be thought of as a connected drawing of lines and vertices on a surface such that, firstly, lines do not cross (other than at vertices;) and, secondly, cutting along all of the lines would cut the surface up into simply connected regions called faces. In other words, none of the cut-out pieces of surface would contain a hole or handle. Thinking about possible drawings on the surface of a tea cup (one with a handle) may clarify the above definition.

The PWT establishes an incredible ubiquity for weaving. There is left no firm foundation for considering maps, triangulations, dessins d'enfants, or any other familiar mathematical bricks, to be more fundamental building blocks of surfaces than weaving.

THE VENDING MACHINE ALGORITHM

Hoping to describe the practical application of the Plain Weaving Theorem in a memorable way, I introduce the Vending Machine algorithm for converting a map into a weave pattern:

Given a map drawn on a surface, place a vending machine midway between the two ends of each edge. Pedestrians will now fully short-cut the corners of the original faces. The pedestrian paths show the paths of the weaving elements. The pesky over-and-under weaving business at the vending machines is settled by choosing a left- or right-handed wood screw. Insert the screw in the middle of each face and incline the nearest weaving elements going around the screw to conform with the inclination of its threads. That being done, the over-and-under business takes care of itself, and you've got a basket.

Undip as a formal language

2011-08-15T06:39:00.000-07:00

A formal language equivalent to undip, and its application to building hamiltonian planar cubic (i.e, trivalent) maps, is described in Shuffle of parenthesis systems and Baxter permutations by Robert Cori, Serge Dulucq, Gérard Viennot (1986):

"...hamiltonian cubic maps are planar maps with a hamiltonian circuit in which all vertices have degree three. In such a map any vertex is incident with only one edge not in the hamiltonian polygon, this edge may be inside the polygon or outside. Thus to build a "Hamiltonian rooted cubic map" one has to choose 2k vertices among the 2n (those incident with inside edges) then draw a planar map inside the polygon (it is easy to see that this can be done in C sub k [the kth Catalan number] ways) and a planar map outside. We have thus also an intuitive proof of the fact that the number of "hamiltonian rooted cubic maps with 2n vertices" is:

Their argument explains a surprisingly simple relation: the number of undip words of length 2n is given by the product of the nth Catalan number and its successor.

To share in the surprise it helps to know that finding hamiltonian circuits in trivalent graphs is sometimes difficult. The hamiltonian cycle problem is a special case of the traveling salesman problem obtained by setting the distance between two cities to a finite constant if they are adjacent and infinity otherwise. In fact the hamiltonian cycle problem in trivalent graphs is NP complete: it is known to be formally equivalent to finding boolean values of the variables that will make an arbitrary expression in symbolic logic evaluate as true (Garey, Johnson, and Tarjan, 1976.) Yet we garner from the above formula the exact aggregate number of rooted (i.e. choose a starting edge and a direction) hamiltonian circuits in planar trivalent maps with n vertices—though our posterity may never find them all.

It may seem a bit inelegant that we must count rooted hamiltonian circuits, thus counting each hamiltonian circuit multiple times—once for each way we could start and go around the circuit—but this kind of counting is very much attuned with a weaver's needs. If we are making a basket, especially a large one, it can matter very much the order in which it is built, so it is good to count our options.

Note that since this counting distinguishes ud and np (for example,) it presumes an orientation. Being a genus zero (planar) map guarantees that the surface our basket is embedded in is orientable. We must still choose one of the two possible orientations: i.e., we must specify which of the two sides of the embedding surface we are looking at. Only then are the baskets ud and np distinguishable.

UNDIP AS A FORMAL LANGUAGE

Starting from the empty word, every word in undip can be formed by a succession of two-letter insertions (ud or np)—between letters, at the beginning , or at the end of the word—and two-letter shuffles of pairs of adjacent left/right characters past each other. Furthermore, the result of such a process is always a word in undip. Therefore the insertion rules and the shuffle rule constitute the formation rules of undip.

THE LEFT AND RIGHT DYCK LANGUAGES

The subset of undip words that can spelled with just the letters u and d are clearly formed using only the ud insertion rule. Such a rule forms the Dyck language on {u, d}. We will call this subset of undip the left Dyck language. Similarly, the subset of undip words that can be spelled with just the letters n and p are called the right Dyck language.

The Dyck language is familiar to us in the ordinary rules for using parentheses. For example, a sequence of parentheses that would be valid in a mathematical expression, such as,

(()())()

can be formed starting from the empty word by successive insertions between characters, at the beginning, or the end of the word, of the two-character sequence ().

UNSHUFFLED UNDIP WORDS

Starting with some word in undip, say

uunddupd ,

the shuffle rule allows us, step by step, to gather the left characters to the front of the word and the right characters to the rear. The end result is an unshuffled undip word. For the word above such a possible sequence of shuffles is

uunddupd
uunddudp
uudndudp
uuddnudp
uuddundp
uuddudnp ,

resulting in the unshuffled word uuddudnp after five shuffle mutations.

DESCENDANCE FROM DYCK BASKETS

Since the anterior portion of an unshuffled word has been formed by ud insertions, it is a left Dyck word, and likewise the posterior portion of an unshuffled word is a right Dyck word. Since each of these portions is, in itself, an undip word, we can employ the converse of the rule that any undip word can be inserted into any other undip word, and thereby separate these two concatenated undip words:

uuddudnp = uuddud + np

Let's see the above process above in terms of the baskets the words describe. We began with the polyhedral (i.e., 3-connected) basket uunddupd and mutated it incrementally through a sequence of five shuffle mutations into the 2-connected basket

uuddudnp .

We then parted it into two baskets, one described by a left Dyck word, the other described by a right Dyck word, or, what we will call a left Dyck basket and a right Dyck basket.

Every step is reversible: we may now rejoin the two baskets and, one by one, invert all of the shuffle mutations until we regain the original basket.

Therefore: Every undip basket is descendant by a sequence of shuffle mutations from the union of a left Dyck basket and a right Dyck basket (either of which may be null.)

This slide show shows the descent of the basket above using paper twogs.

Making new undip words

2011-08-12T16:29:00.000-07:00

Any undip word can be inserted anywhere in any other undip word. The resulting basket will be only 2-edge-connected at the splice. Shuffling can fix this. Shuffling is when adjacent letters that are left/right (e.g., up) or right/left (e.g., pd) switch places. Shuffling is always permissible.

Conversely, anywhere an undip word appears in another undip word (that would most commonly be ud or np) it can be deleted.

The pairs du and pn can also be deleted anywhere they appear. I call this a rewire mutation since it redirects a photon. The converse, inserting these pairs, cannot be relied upon to be viable. There is a special context where absorb/emit events can be inserted: between emit/absorb events on the same side.

The most fun way to make new undip words is to doodle them. Using graph paper make a doodle that stays on the graph paper lines. The rules of the game are that your doodle must start and end at the same place (the origin) and never go below or to the left of that point. In math terms it must not cross the x or y axis.

The path is encoded to an undip word in this way: each step up is a u, each step down is a d, each step out (i.e., to the right) is an n, each step back (i.e.,to the left) is a p.

Make a Pony-O Basket from a Word

2011-08-11T05:21:00.000-07:00

I'll just show you how to do it here. Details on the tiny bit of particle physics involved and on the undip language itself are covered in my 15-minute video, Make a Basket from a Word.

THE BASIC MOVE: QUOIT-THROUGH-THREAD

Three Pony-O's can be interlooped in what may properly be called a Mrs. Bright's knot (a three-way version of knot #2425 in The Ashley Book of Knots,) but to make things easier for us to remember, we'll call it Quoit-through-Thread, or sometimes just QTT. Try this right now:

Step 1: Hold NEEDLE upright.

Toss QUOIT on NEEDLE.

Insert THREAD through NEEDLE.

Pull QUOIT through THREAD.

Voila!

Once you feel comfortable making Quoit-through-Thread as shown, try inserting THREAD from the left so that QUOIT ends up on the right. Another way to do this variation is to feed THREAD halfway through every time and just pull QUOIT up through the side you want it on.

In making a Pony-O basket, QUOIT always represents a photon, while NEEDLE and THREAD always represent the electron in differing energy states. In the pictures above, the photon color is green, and the two energy colors of the electron are purple and pink.

UNDIP

Undip is a language that tells stories about an electron. We'll choose this undip word,

uunddupd,

and find out what shape it makes. Along the way you'll hear the story of the electron and learn to read undip.

You need three colors of pony-O's, 4 pony-O's of each, plus one extra pony-O of any color you like. (You'll always need three colors, and of each color you will always need half the number of letters in the undip word; you will also need one extra of any color to finish off the work.)

Hopefully one of your colors will really stand out. Make that color your photon color. In the photos I'm using bright green as my photon color.

The other two colors are energy colors. The energy of an electron always changes when it emits or absorbs a photon, so our electron's energy state alternates between these two colors at each photon event.

Print or write down the undip word above in lowercase letters. Then turn the page 90 degrees so that you are reading the word from the bottom up.

To begin, choose a pony-O in one of your energy colors. It will become NEEDLE in your first Quoit-through-Thread.

The first letter in this undip word, 'u,' says that our electron emits a photon to the left. Choose a pony-O in your photon color and use it as QUOIT. Emitting a photon changes (decreases) the energy level of an electron, so use the other energy color for THREAD. Make sure QUOIT ends up on the left at this event since we are emitting a photon to the left.

If that QTT went well, you've completed your first photon event.

The next letter is also 'u.' The undip word says that our electron emits another photon to the left. Use the free end of the OLD THREAD (it has the current energy color) as NEEDLE in the next QTT. Repeat the steps above to emit another photon on the left. Remember to change your energy color at each event.

The next letter is 'n.' The undip word says that the electron emits a photon to the right. That's going to be easy: its just like the first two events except that QUOIT ends up on the right. Remember to change your energy color; and by the way, never let go of the current energy state! A good electron never loses track of its energy. For that matter, don't let the work start getting twisted up or your electron will start confusing left and right.

If you set your work down,failing to mark where you were, note that there are only two energy-colored Pony-O's, those are the first and the last. Comparing the first few events with the begining of the undip word should sort out which end is which.

The next letter 'd' is a little different. The undip word says that at this point in the story our electron absorbs a photo on the left. As you might expect, we'll be bringing a photon-colored QUOIT in from the left, but this time it is one of the photons already emitted. We find that photon by running a hand back along the left side of the work. The first loose end we come to is our QUOIT. This time, put QUOIT through THREAD as the first move; then QUOIT on NEEDLE; and then THREAD through NEEDLE. You may choose to always make QTT in this order, but I tend to fumble with it. Absorbing a photon always changes (increases) the energy level of a photon, so THREAD is a different color from NEEDLE this time as well.

The next letter is another 'd'. The undip word says that our electron absorbs another photon on the left, so repeat the previous event, again tracing your hand back along the left side of the work to find the photon to use as the quoit, and bring it in from the left.

The next letter is 'u': again we emit a photon to the left.

The next letter is 'p'. That says that our electron absorbs a photon on its right. This time we trace a hand back along the right side of the work to find the photon we will bring in from the right side. You'll find this photon is a long way back, but as always, its the first one we come to.

The last letter is 'd.' An undip word tells a story that implicitly repeats, so the story is not over just because we have come to the last letter of the word. We are headed back to where we started (and our basket will be finished) but our electron will be headed out for another lap. The 'd' says that the electron absorbs a photon on the left, so trace back along the left to find the photon and bring it in from the left as QUOIT.

At this point we want to bring the only remaining free end (notice that it is none other than our first energy state) as THREAD. This presents a problem because this THREAD is already attached to the work. So this time we toss an extra Pony-O named OUTIE over THREAD before beginning the knot. Things now proceed normally until we would normally pull THREAD through NEEDLE: we pull OUTIE through instead. OUTIE, can be tied off in an a snug overhand knot to keep things from unravelling and to mark where it all began.

Bravo! You've done it!

undip dictionaries published

2011-08-10T13:03:00.000-07:00

I have just published unabridged, illustrated dictionaries for the undip words of 2, 4, 6, 8 and 10 letters. The illustrations, unfortunately, are just the lattice walks corresponding to the words—no basket shapes yet.

Viable Adjacent Letter Mutations

2010-10-06T12:54:00.000-07:00

There are some two-adjacent-letter edits (substitutions, insertions, and deletions) that can always be made in an undip word and the result will be another undip word. These special edits, viable adjacent letter mutations, or val mutations, intrinsically satisfy the undip grammar rules, the larger context of the two original adjacent letters need not be consulted. The term "viable," borrowed from biology, here means that the character string that results from a val mutation will indeed be a word in the undip language (and it will therefore weave unambiguously to a specific basket shape phenotype.)

In the tables below, all of the val mutations are summarized in truth table format. The first of the original adjacent letters labels the row, the second the column. The letters that will replace the two original letters are entries in the table, with e symbolizing deletion of both letters, and a blank entry indicating that no val mutation of that type (substitution, insertion, or deletion) can be made for those two letters.

Some other two-adjacent-letter edits may be viable in certain special contexts, for example insertion of the reversed spikes du and pn , but in the worst case, full context information would be needed to determine if the insertions are viable. In this sense, what are termed here val mutations are context-free.

Gene-Splicing Baskets

2010-10-06T05:43:00.000-07:00

Starting with undp, an undip word for tetrahedrane,

concatenate ud, an undip word for acetylene...

...and get undpud, or benzvalene.

Insertion of undip words works just as well as concatenation. At any place in an undip word, insert another undip word and the result is a new undip word describing a hybrid shape. The new shape is 2-edge connected where the two original shapes are tenuously joined.

The structural weakness of this 2-edge join can later be healed by viable adjacent-letter (val) mutations. Val mutations are substitutions, insertions, or deletions of two adjacent letters that can be made without reference to context because they intrinsically satisfy the undip grammar rules.

Twongs Thronged at NY Maker Faire!

2010-09-29T13:16:00.000-07:00

Visitors thronging the Twongs Table at the New York Maker Faire, September 25-26, 2010.

That's me in orange. Some tried making the carbon chemistry models (annulenes) displayed in steel, but most went freeform.

All ages advanced to level 101: having fun.

The steel models wore their undip codes attached.

Tetrahedrane in foreground, acetylene in back.

Catalan Numbers and Baskets

2010-09-17T07:10:00.000-07:00

How many undip words are there?

The famous Catalan numbers turn up in many places ( see "Exercises on Catalan and Related Numbers" and "Catalan Addendum" by Richard P. Stanley.) One of the classic examples is counting the number of ways 2n people seated around a table can simultaneously form n handshakes without crossings. The answer to this problem is the nth Catalan number. For example, the Catalan numbers for n = {0, 1, 2, 3, 4, 5} are {1, 1, 2, 5, 14, 42}.

Another set counted by the Catalan numbers are the number of words in the Dyck language that contain n pairs of parentheses. The Dyck language comprises all strings of open and close parentheses that follow the usual rules of arithmetic expressions. For example:

()

(()) ()()

((())) ()(())) (())() (()()) ()()()

etc.

The undip language is a shuffle of two Dyck languages: a {u,d} language and an {n,p} language. We can think of {u,d} as {(,)} and {n,p} as {[,]}, but unlike a Dyck language on two types of parentheses, in a shuffle of two Dyck languages the two types of parentheses ignore each other grammatically speaking. For example, a word such as:

( [ ) ]

is permitted.

R. Cori, S. Dulucq, and G. Viennot explain how the Catalan numbers are related to the planar hamiltonian cubic maps (the structures described by undip codes) in "Shuffle of Parenthesis Systems and Baxter Permutations," Journal of Combinatorial Theory, Series A 43, 1-22 (1986):

"...hamiltonian cubic maps are planar maps with a hamiltonian circuit in which all vertices have degree three. In such a map any vertex is incident with only one edge not in the hamiltonian polygon, this edge may be inside the polygon or outside. Thus to build a 'Hamiltonian rooted cubic map' one has to choose 2k vertices among the 2n (those incident with inside edges) then draw a planar map inside the polygon (it is easy to see that this can be done in Ck ways*) and a planar map outside."

*This is easy to see because it is essentially the handshaking problem.

A map is rooted by distinguishing a vertex and direction. In a hamiltonian circuit this is combinatorially equivalent to labeling all the vertices, since, given a direction and a place to start, we can reliably label the vertices with sequential integers. Working with a rooted map, every rotation of a pattern counts as a distinct pattern because the root occupies a different place in each rotation. Counting rooted maps exhaustively counts all of the possible undip codes even when they trivially encode the same shape by virtue of merely starting at a different location on the hamiltonian cycle.

Cori, Dulucq, and Viennot go on to show that the number of rooted hamiltonian planar cubic maps are counted by the product of two sequential Catalan numbers. For a hamiltonian circuit with 2n vertices the number of maps is the product of the nth Catalan number and the (n+1)th Catalan number.

Tthe number of undip words of length 2n for n= {1, 2, 3, 4, 5} are {2, 10, 70, 588, 5544}. This is sequence A005568 in the On-Line Encyclopedia of Integer Sequences (OEIS).

For better or worse, there are a great many more undip words than there are shapes to be described by them. Synonyms will abound.

O-Knitting

2010-09-10T11:45:00.000-07:00

Making an o-knitting vertex, Step 1: Hold Needle upright.

Toss Quoit on Needle.

Feed Thread through Needle.

Pull Quoit through Thread.

Voila! a completed vertex.

Close-up of completed o-knitting vertex.

All sorts of things that I'll call o's are available to the craftsperson: rubber bands, ponytail holders, potholder loops, etc. O's can also be made at home by slicing across a can or plastic bottle, or anything else of tubular cross-section. O's can be knit together to form 3D shapes without the increases and decreases traditionally depended upon in knitting and crochet. O-knitting can optionally be guided by a string of letters drawn from a four-letter alphabet, what I call an undip word, that describes the step-by-step construction of a surface. Using undip words, o-knitting becomes a sort of genetic knitting.

There are only two big things to learn about o-knitting: how to make a vertex, and how to follow an undip code. Learn those two things and you will be a able to build a spaceship on a desert island, or at least a floppy grass model of one.

An o-knitting vertex is an inter-looped union of three o's. An o-knitting vertex is a reciprocal structure. That is, each of the o's plays the same role in the union. We'll give each o a name according to how it first enters the union, but by the time we are done making the vertex they'll all be equivalent. An o-knitting vertex is a three-way version of Mrs. Bright's (four-way) True Lovers' Knot (Ashley Book of Knots #2425.)

OK, let's make an o-knitting vertex. The first o is called Needle. Except at the very first vertex (call it the origin,) Needle will already be attached to the work. Hold Needle with its free end upward.

The second o is called Quoit. Quoit is always free at both ends. Toss Quoit over Needle.

The third o is called Thread. Feed Thread through Needle. It is best to always feed Thread from the right side (or always from the left side, if you prefer.) Feeding from the same side makes vertices that are all of the same handedness, giving the fabric a more even look. Thread will be free at both ends when making u and n vertices, but already in the work when making p and d vertices.

Now feed Quoit through Thread (i.e., through the end of Thread that pushed out through Needle.)

Voila! One vertex made. 3D shapes are made by repeating the above moves.

3-D shapes may be specified by an undip word or genotype, a character string made up of the four emoticons: u, n, d, and p.

For example, a genotype for the cube is

nuupdd .

The the letters are called emoticons because they are meant to be read with the head tilting sideways (toward the right) and their meanings are visually obvious—no need to wake up the left side of the brain at all. The four o-knitting actions they encode are:

"Open left," meaning: "make a new vertex and leave the o on the left side dangling," (i.e., continue to the right. )

"Open right," meaning: "make a new vertex and leave the o on the right side dangling," (i.e., continue to the left.)

"Close left," meaning: "make a new vertex employing the nearest dangling o on the left side."

"Close right," meaning: "make a new vertex employing the nearest dangling o on the right side."

(Figure out for yourself which emoticon encodes which action.)

Note that at a close vertex the roles of Needle and Thread can be assigned so that Thread enters Needle consistently from the right (or, alternatively, consistently from the left.) A switch causes no confusion about how to continue, since just a single o is left dangling after a close vertex.

You have to work consistently from the outside of the piece (or consistently from the inside.) Early on this will mean taking care that o's do not get twisted. At the end, should you find you have made the enantiomorph of what you intended—no problem. Just evert the piece through one of its openings.

Quoit must always be free at both ends, but at the final vertex all three o's will already be attached to the work. The final vertex must be joined by some other technique. The simplest way is to add a fourth o as Quoit, making the last vertex a regular fourway Mrs. Bright's knot. The extra o is left dangling, permanently marking the origin (and terminus) of the undip word.

Hansel & Gretel's Hint: mark your very first o with a twist tie or special color—should you get lost, you can can retrace the word from the beginning.

Embedded graphs come in families of four

2010-08-31T12:28:00.001-07:00

Cubic graph (the dual)

Triangulation (the primal)

Radial graph

Medial graph

Kagome weave

Anyam Gila

In unit weaving we are constantly dealing with families of four closely related graphs: a triangulation (the primal graph), a cubic graph (the dual graph), a medial graph, and a radial graph. Kagome (triaxial weaving) is closely related to the medial graph of a triangulation. Anyam Gila (or "mad weave"), a triple-layered version of kagome, has an outward appearance that suggests the radial graph of a triangulation.

Some facts from the Handbook of Graph Theory:

1. An embedded graph M is a medial graph of some graph G if and only if M is 4-regular and the faces can be properly 2-colored.

2. An embedded graph R is a radial graph of some graph G if and only if R is bipartite and every face is a quadrilateral.

3. The medial graph M of an embedded graph G is identical to the medial graph of the dual G*. The radial graph R of G is identical to the radial graph of the dual G*. The embedded graph and its dual are the only two graphs whose medial and radial graphs are M and R respectively.

Any surface-embedded graph can play the role of "primal," and it is guaranteed to have a dual, medial, and radial, all of which are discoverable through simple constructions called map operations. It is a convenience of speech that we identify one graph as the primal and the other as the dual: the roles could just as easily be reversed with no effect on the rest of the foursome. The same, however, is not true for the medial and radial (which are also mutually dual,) because radial graphs and medial graphs each have special characteristics as indicated in Facts 1 and 2 above. Thus, most graphs belong to only one foursome: the one formed when they are the primal (or equivalently the dual.) The few graphs that qualify as medial (or radial) graphs belong as well to a second foursome: the one where they are the medial (or radial.)

The familiar square grid makes for a special case. It is dizzyingly at once self-dual, self-medial, and self-radial. This deep symmetry of the grid pattern helps explain why 10,000 years of biaxial weaving has not gotten us very far in understanding weaving more generally.

When plain weaving is not in some artificially arranged conformation, just two threads cross at each crossing. A graph of a plain weaving (crossings being represented by vertices and threads being represented by edges) is therefore four-regular (i.e., exactly four edges meet at each vertex.) That satisfies the first requirement in Fact 1.

The relevance of the second requirement in Fact 1 can be seen from an observation by Snelson (U.S. Patent 6,739,937), that each thread in a plain weaving is a boundary between a left-handed opening and a right-handed opening. Such an arrangement is only possible if the fabric openings can be properly 2-colored (such a coloring is popularly known as a chess-coloring or checkerboard-coloring.)

The necessary and sufficient requirements for a graph to be a medial graph are thus the same requirements necessary and sufficient for a graph to specify a plain weave: the 4-regular graph specifies the two-dimensional arrangement of threads, and the 2-coloring of its faces tells us which openings are to be left-handed or right-handed. The handedness of the openings, in turn, tells us how to arrange the threads at each crossing, in the third dimension, to produce a true plain weave.

In this light, Fact 1 establishes that every medial graph describes two enantiomorphic plain weaves (one for each of the two alternate left/right color assignments.)

In the same light, the converse assertion in Fact 1 (i.e.: if M is 4-regular and the faces can be properly 2-colored, then M is a medial graph) establishes that no plane weave exists that is not described by a medial graph.

In short, weaving has found the light switch after thousands of years of fumbling in the dark:

1. We now know that every compact surface can be plain-woven-- no matter the topological complexity or the orientability of the surface. (The term "compact" merely rules out some mathematically defined surfaces that cannot be realized by any technological means. In layman's terms we can plain-weave any surface.)

2. We can plain-weave that surface in essentially any pattern (we are not limited to familiar biaxial or triaxial weaves.) Any graph, any drawing of edges and vertices we choose to put on the surface, can direct the weaving via its medial graph.

3. We know constructively how to proceed in every case.

4. We know that our construction process is universal: there exist no other plain weaves but those described by medial graphs.

We have 1-3 above from the 2009 topological proof by Akleman, Chen, Xing, and Gross (see my earlier post Proving Weaving) I believe the universality result is new.

Undip codewords as lattice walks

2010-08-29T12:52:00.000-07:00

Any undip word can be identified with a 2D lattice walk where the allowed steps are N, S, E, W, the walk begins and ends at the origin (such a lattice walk is called a loop), and the walk is furthermore confined to the first quadrant (quarter plane).

Identify 'u' with an North step, and 'd' with an South step (mnemonically 'up' and 'down'). Similarly identify 'n' with an East step and 'p' with a West step.

The "balanced parentheses" rules for undip words (where |x| denotes the number of occurences of the letter 'x') are:

|u| = |d|

|n| = |p| ,

These rules guarantee that total South steps equal total North steps, and total West steps equal total East steps; thus, if a codeword-designated walk begins at the origin, it will end at the origin.

The "nested parentheses" rules guarantee that the walk stays in the first quadrant. The rules are:

|u| >= |d|

|n| >= |p|

for any predicate of an undip word.

In other words, at no point in the spelling of an undip word will there have been more d's than u's, or more p's than n's. On the lattice this means that the walk can never go south or west of the origin-- it is confined to the NorthEast quadrant.

Undip codes and Euler's Formula

2010-08-29T11:51:00.000-07:00

Any graph embedded in the sphere must obey Euler's formula:

F - E + V = 2 ,

where F, E, and V are the number of faces, edges, and vertices. Since every hamiltonian cubic graph embedded in the sphere has a valid undip codeword, a reasonable question is how (and whether) having a valid undip codeword can guarantee compliance with Euler's Formula.

Euler's formula is a bit simpler for cubic graphs. Cutting a cubic graph at every mid-edge, leaves a disconnected set of vertices, each still holding on to three half-edges. Thus,

E/V = 3/2 .

That fixed E/V ratio reduces Euler's formula for a cubic graph to

F - V/2 = 2 ,

F = V/2 + 2 .

In a valid the undip codeword there is one letter for each vertex. For every open letter, 'u' and 'n,' there is a matching close letter, 'd' and 'p'. Therefore a count of the occurrences of d and p, |d, p|, will count one half of the vertices:

|d,p| = V/2 .

Euler's formula then becomes

F = |d,p| + 2 .

It is easy to see that in weaving a valid undip codeword this rule is always obeyed. Each close letter, 'd' or 'p', completes a face, until we come to the final close letter. The final close letter also completes the hamilton cycle and thereby closes an additional face on both the left and the right-- that provides the final "+ 2" faces.

What can undip codewords code?

2010-08-27T12:57:00.001-07:00

Twongs and twogs can make more shapes than the four-letter undip code can code.

A graph must have a Hamilton circuit in order to be undip encoded. (Note that Hamiltonicity is a property of the graph, not the embedding.) That leaves out cubic graphs with self-loops (cubic pseudographs proper) since they can never be Hamiltonian. Only cubic multigraphs can be undip coded.

Furthermore, the embedding must be in the plane (or equivalently the sphere) in order for the coded side bonds to link up predictably. On a higher genus surface, the whole surface area might be encoded in the predictable planar way, but there will remain a closed curve (i.e., the polygon of the plane model, see A Combinatorial Introduction to Topology by Michael Henle) that cannot be seamed across without encountering a surprise.

The photo above shows a digonal prism. Even though a digonal prism is a graph embedded in the sphere, it is not considered a polyhedron by most definitions. For one thing, it contains two-sided faces (digons); for another, it is only 2-edge connected. (Cutting just the two edges shown vertical in the photo would separate the graph into two components.) Note that these are properties of the graph itself, not the embedding. Graphs that are only 1-edge or 2-edge connected make weak structures but they certainly are of sculptural interest. Polyhedron or not, 'udud' codes the digonal prism nicely.

Taking the adjective "plane" to mean "embedded in the plane or sphere," the undip code can encode Hamiltonian plane cubic multigraphs.

What can twongs make?

2010-08-27T11:20:00.001-07:00

Twongs and twogs can make 3D embeddings of cubic pseudographs.

A graph is called cubic if three edges meet at each vertex. Simple graphs permit only a single edge to link two distinct vertices, multigraphs allow more than one edge to link two distinct vertices, pseudographs also allow a vertex to link to itself (i.e., form a self-loop.) A graph is an abstraction: a set of symmetrical relations (edges) between pairs of members of a set (the set of vertices). For example, the friendships (edges) between persons (vertices) listed in a phonebook. Such an abstraction has no geometry until we make some decisions not specified in the graph itself in order to place (embed) its vertices and edges in 3D space, or on the Euclidean plane, or on some other surface or in some other space. Sometimes a given graph can be embedded in a space in fundamentally different ways, e.g., a left-handed and a right-handed version. The embedding, not the graph itself, is our guide to these important practical details. See Topics in Trivalent Graphs by Marijke van Gans for a clear mathematical exposition.

If twongs and twogs are made long enough, they can be used to realize any 3D embedding of a cubic pseudograph. The construction above is an embedding of the smallest cubic pseudograph having loops. I call it loop-loop. An embedding of the smallest cubic pseudograph without loops (thus also a multigraph) is shown below. I call this one bang-bang.

twongs

2010-08-15T20:16:00.001-07:00

These are what I call twongs.

A twong is a helical length of wire that has been bent in four places. Twongs are made by twisting up a pair of wires (these particular ones have been twisted to a helical wavelength of about 5 wire diameters), unravelling them, cutting them to length (these have been cut to a length of 12 helical wavelengths), and then bending. I have been working by hand, so I have been limited to 9 gauge (0.14 inch diameter) steel wire and smaller. Wire is made over a vast range of diameters, so twongs can be almost any size.

The main thing about twongs is that they twine together, three at a time, to form vertices. I've made a video about twining them together. With enough twongs you can make any shape having exclusively 3-valent vertices (three edges meeting at a vertex.) The tetrahedron, cube and dodecahedron are famous 3-valent (i.e., cubic) polyhedra, but there are many more. For example, there are 14,501 isomers of the dodecahedron, that is, different shapes but all with the same number of faces, vertices, and edges as the dodecahedron, and they are likewise all 3-valent. The C-60 buckyball is also all trivalent. Its isomers are effectively uncountable, being in excess of 10 to the 22nd. Yikes!

The are so many cubic polyhedra that, given enough vertices, we can use one to approximate any simple closed (i.e. genus zero) surface. The approximation is never smooth because all lengths are the same, nonetheless, there are many cases where a crinkly surface is a good enough, or where a crinkly surface can be made smooth by some mechanical process. In any case, the alternative--custom cutting every piece (I've tried it)--is a royal headache, and no custom-cut part is ever re-useable.

An astonishing thing about genus zero cubic graphs (let's just toss out the very small number that are non-Hamiltonian) is that they can be identified with words in a language having a very simple grammar. Formally the language is known as the shuffled Dyke language on two types of parentheses. Instead of parentheses we will want to use the following letters:

u, n, d, p

corresponding to (look at them tilting your head to the right) the following twiner's actions

"open left", "open right", "close left", and "close right"

The moves are as follows:

To start, pick up a very first twong and mark it with a twist-tie. This is insurance against getting lost--you can always retrace from the beginning if you know where that is. It also symbolizes that the very first twong is the work in progress. At any later vertex, at least one twong will be already part of the work in progress.

The first letter is always an "open" action, i.e., 'u' or 'n'. In an "open" action you just build a vertex--that's the same for "open left" or "open right." The difference comes when you exit the newly built vertex. To leave a twong "open (on the) left", we must build onto the right twong, Likewise to leave a twong "open (on the) right" we must build onto the left twong. That's all there is to 'u' and 'n,' they just tell us which way to go next.

Close actions require us to incorporate a previously placed twong into the current vertex. According to the letter, we are to look either to the left or the right for this previously placed twong. If there is more than one available on that side we simply choose the nearest one on that side (i.e., most recently placed). This is the same way nested parentheses close, hence the connection to parenthesis languages. Departing a close action is simple since only one of the three twongs will still have a free end.

The last vertex is always a close action. Implicitly, the first twong (the one marked by the twist tie) must be incorporated in this vertex along with the twong indicated by the final letter.

I have more about these "undip" codes in this year's Proceedings of the ISAMA.

Knit Anything

2010-03-07T15:14:00.000-08:00

M. Gopi and David Eppstein have presented an algorithm that edits a surface triangulation until it admits being cut up into one long strip of triangles. The use of this algorithm has been in computer graphics. It turns out that a strip of triangles is one of the most efficient ways to describe a surface for display. It is also just what is needed to construct a fabric of any shape while working in a continuous, systematic order.

In order to go from a list of triangles to a fabric that assembles the triangles in the intended way, the knitter needs to be able to make triangles in all the possible contexts they are found in the work.

I have come up with the Triangle Context Chart as an aid to the knitter in recognizing and dealing with this small set of triangle contexts. There are in fact sixteen triangle contexts, resulting from four binary possibilities:

The triangle is either an interior triangle or an exterior triangle (the only exterior triangles are the first, the cast-on triangle, and the last, the cast-off triangle.)
The yarn enters either from left or right of the triangle base.
The exterior edge of the triangle (i.e., the edge that is not interior to the triangle strip) is either a temporary selvage (open) or it is an entrelac (close), meaning it picks up stitches from the selvage of a previously knit triangle.
The exterior edge is on the left or the right.

Since it is obvious that the first triangle in an instruction must be the cast-on triangle, and the last is cast off triangle, the first binary possibility does not need to be explicitly stated.

Also, which side the yarn enters on is an inevitable consequence of the knitting in the preceding triangle, and the independent choice at the very start of the knitting is not usually important, so the second binary possibility can go unreported as well.

That leaves four possible contexts needing to be reported for every triangle in the knitting: open left, open right, close left, close right.

A convenient way to write down a sequence of these four triangle contexts is with this emoticon code:

u , n , d , p .

Hint: look at the letters like smileys, but inclining your head toward the right.

I call this the undip code (accent on the first syllable of 'undip'.)

In undip, a word for the tetrahedron is:

u n d p ,

or synonymously,

n u p d .

Reference:

Gopi, M., Eppstein, D., "Single-Strip Triangulation of Manifolds of Arbitrary Topology." Proc. 25th Eurographics 2004.

Proving Weaving

2010-02-23T12:33:00.000-08:00

The Plain-Weaving Theorem

Akleman, Chen, Xing, and Gross (ACXG) have published a proof that every polygonal mesh describes a plain-weaving (a term to be precisely defined below.) If so inclined, we may count two plain-weavings by considering weavings differing only in textile handedness (indicated by the helical pattern of threads around a specified opening in the fabric) to be distinct.

(Note that any weaving can theoretically be everted—turned inside-out—through an opening. While this does not alter the textile handedness of the work, it does change the handedness of the work as a whole. For example, eversion turns a right hand glove into a left hand glove. So it may fairly be said that the everted version does not weave the same surface. Nonetheless, the same set of weavers, woven in the same handedness, may weave either surface. The basket maker will need a hint to resolve this ambiguity.)

ACXG's result is fundamental. Their proof is fully three-dimensional and topological, so there can be no objections as to its physical reality. The proof leaves no escape for a compact surface of any sort -- all compact surfaces, be they orientable or non-orientable, high-genus or low, are doomed to be woven as baskets. The escapees are the non-compact surfaces, i.e., surfaces of infinite extent, or infinite topological genus, or having excluded interior points or open boundaries—but such are not buildable by any method.

And there is also no escape for any particular kind of mesh. Their result, which I will take to calling the Plain-Weaving Theorem (PWT,) states that all polygonal surface meshes describe a way to weave the surface. There is great difficulty imagining any way to subdivide a surface into local neighborhoods that is not in effect a polygonal surface mesh. Admit it or not, computer scientists are doomed to be virtual basket weavers for the rest of history.

Having this 3D theorem in hand, I want to turn to a purely 2D representation of plain weaving which is easy to visualize, easy to characterize as a mathematical object, and probably sufficient for all artisanal purposes.

The Definition of Plain-Weaving

I adopt ACXG's definition of plain-weaving—which differs from common usage in the textile field. In their definition, a plain-weaving "consists of threads that are interlaced so that a traversal of each thread alternately goes over and under the other threads (or itself) as it crosses them." This definition takes in some weaves such as the kagome (also known as open hexagonal or triaxial) weave that are not considered "plain" in the textile field, but the PWT rewards us with the insight that all plain-weaves newly defined are really the same thing and can be intermixed freely.

Weaving and Chess-Colorings

Kenneth Snelson, in the specification of his patent on 3D weaving, U.S. Patent 6,739,937, makes a significant observation: we can treat weaving as a 2D arrangement of openings rather than a 3D arrangement of threads. To turn the old saw around, Snelson is saying we should watch the hole, not the donut.

As Snelson observes, the openings in a plain-weave fabric have a handedness that can be compared with the handedness of a screw-thread. In going from over-one-thread to under-the-next whilst going around an opening, the threads have a ramp-like geometry. If we arbitrarily choose a direction of travel around the periphery of the opening, and identify that direction with the direction of the curled fingers, then using the ramps in this direction converts the advancing movement into a motion in a perpendicular direction. We can identify this perpendicular direction with the direction of the thumb extended. Uniquely only a left or a right hand is capable of carrying both of these identifications. We can therefore unambiguously label every opening in a weave as right or left, R or L, or perhaps color code them black or white. Since no reference has been made to a side of the fabric, the handedness of the openings is intrinsic to the weaving: it matters not which side we view or whether the work is everted or not.

Also, there can be no question that the threads in a plain-weave agree on the handedness of any opening they share—otherwise they would not be able to reach a mutual arrangement about whose turn it is to go over or under where they cross. Like a circle of fallen dominoes, they must all lean one way.

Snelson observes that adjacent openings (i.e., openings on opposite sides of the same thread) have opposite handedness. This follows almost anatomically: if two hands have curled fingers pointing in the same direction, and extended thumbs pointing in the same direction, they surely must be a right and a left.

A coloring of the faces of a map with two colors, say black and white, such that adjacent faces have different colors is called a chess-coloring (I prefer this shorter term over "checkerboard coloring") Not all maps can be chess-colored, but a map operation, medialization, is known which converts any map into a chess-colorable map (Deza and Dutour.) The resulting map is called the medial of the original map (itself called the primal), and the result of medialization is the same whether we start from the primal map or its dual. In map operation notation (see Diudea et al. for an explanation of the notation):

Me(M) = Me(Du(M))

This is the result reported in ACXG that a mesh and its dual describe the same weaving. As Deza and Dutour have pointed out, medialization can be applied to any map (surface-embedded graph) to produce a chess-colorable map, hence every surface-embedded graph has a plain-weaving discoverable through this map operation.

In knot theory terms, a plain weaving is an alternating link. The medial graph is the projection (or more properly the shadow when crossing information is omitted) of an alternating link. The chess-coloring of the medial graph corresponds the checkerboard-coloring of the link projection, and the primal and dual maps above are the two Tait graphs of the link projection (see explanation of terms in Dasbach and Lowrance.) Because the link is alternating it is described in full by its chess-coloring.

Mathematically the study of plain-woven baskets reduces to the study of chess-colorings on surfaces, and such a chess-coloring contains essentially all the information the weaver needs to weave the basket.

References:

Akleman, E., Chen, J., Xing, Q., and Gross, J. L. 2009. Cyclic plain-weaving on polygonal mesh surfaces with graph rotation systems. ACM Trans. Graph. 28, 3 (Jul. 2009), 1-8. DOI= http://doi.acm.org/10.1145/1531326.1531384

Snelson, K., U.S. Patent 6739937, Space Frame Structure Made by 3D Weaving of Rod Members.

Deza, M., and Dutour, M., Zigzags and central circuits for 3- or 4-valent plane graphs, http://www.liga.ens.fr/~deza/Sem-ZigCc/ZigCcConf.pdf

Diudea, M., et al., 2003, Leapfrog and Related Operations on Toroidal Fullerenes, Croatia Chemica Acta, 76 (2) 153-159, http://pubwww.carnet.hr/ccacaa/CCA-PDF/cca2003/v76-n2/CCA_76_2003_153-159_diudea.pdf

Dasbach, O. and Lowrance, A. 2010. Turaev Genus, Knot Signature, and the Knot Homology Concordance Invariants, http://arxiv.org/pdf/1002.0898

Convolutions as Weaving

2008-12-30T16:58:00.001-08:00

Brain contours rendered as triaxial weaving. Brain model provided courtesy of INRIA by the AIM@SHAPE Shape Repository.

One less thing to worry about.

2008-12-12T08:42:00.001-08:00

Most of my weaving experience has been with twogs, which are very short weavers that only run from one crossing to the next. Since all the twogs are usually the same length, the only way to make the basket surface curve is to connect the twogs in rings of five or seven-- or any ring number other than six (which would produce flat weaving.) One is constantly aware of ring number when weaving twogs. What are naturally called "rings" when weaving with twogs, are more naturally called "openings" when weaving with long weavers. This view of "Olivier's Fingertip" shows that the openings do not all have the same number of sides. I am happy to report that while doing the weaving I was completely unaware how many sides were in the openings I made. Once a weaver has been started in its correct position, it can only weave one way.

Weaving "Olivier's Fingertip"

2008-12-11T15:48:00.001-08:00

Here I am in the early stages of weaving the sculpture "Olivier's Fingertip." Later, as the piece got bigger and deeper, I shifted to working on my lap. That's the cardboard maquette on my right for reference-- it wasn't really needed. Unfortunately the bottle of rubber cement nearby was constantly needed in the nearly losing battle to keep paper templates attached to aluminum weavers.

Weaver Paths

2008-12-11T08:15:00.001-08:00

The path of any particular weaver is rather chaotic. Some are short, some are straight, but then there are ones, like weaver 28 in "Olivier's Fingertip," that loop all over the place. This computer-generated view is from inside the fingertip, looking toward the distal end (the fingernail is on top.) The triangle mesh could probably be edited to minimize outliers like this one, but in any case the need to be able to splice weavers is evident. All the weavers in "Olivier's Fingertip" are unspliced. Ones like 28 are a little too long.

Color Coding

2008-12-10T07:09:00.001-08:00

Here, interlocked, are the first six weavers for "Olivier's Fingertip." The weavers are thin sheet metal with their paper templates still glued on top. I started at the same place I had in the maquette-- though after that I got a little lost, and the weaving didn't go as smoothly as the first time. My starting point is the crossing of weavers that are rather arbitrarily numbered 37, 38, and 00.

In my numbering system palindromes are not allowed, i.e., because 01 is used, 10 must be skipped. Similarly, because 12 is used, 21 must be skipped. This allows a color-coding that is based purely on color combinations, not color order. Up to 55 weavers can be coded with two color stripes in this way. The association between colors and numerals is the same as in the standard resistor color code used in electronics:

0 = BLACK

1 = BROWN

2 = RED

3 = ORANGE

4 = YELLOW

5 = GREEN

6 = BLUE

7 = VIOLET

8 = GRAY

9 = WHITE

I substituted pale lavender for white in order for the stripes to show up on the white paper. The first crossing (38, 37, 00) becomes (orange/gray, orange/violet, black/black.) While weaving you are only matching color pairs, not thinking about their numerical equivalents, but the numerical equivalents are useful in keeping piles of loose weavers organized.

Cardboard Maquette for "Olivier's Fingertip"

2008-12-09T13:49:00.001-08:00

To allay my concerns that the weaving would get too complicated for me (especially because of the self-crossing weavers,) I first made a posterboard maquette for "Olivier's Fingertip" at 58% scale. By chance I found a good order of working, and the weaving went smoothly.

Punching and Cutting

2008-12-09T13:38:00.001-08:00

To simplify cutting, weavers and their glued-on templates are pre-punched with a triangular punch at the sharp indentations of the profile. I slightly rounded the forward corner of the punch with a file to give the cuts a gentler radius. After punching, making the remaining scallop-shaped cuts properly requires both left- and right-handed scissors or shears. Since I have never mastered left-handed scissors (with either hand,) I first make the easy right-handed cuts from the front, looking at the template. Then I flip the work over and make the completing cuts from the back side, working without the aid of the template.

Packing Weavers

2008-12-09T13:18:00.001-08:00

The weaver templates must be packed closely together to avoid wasting material when they are cut out. I don't have a good way of doing this in software. Instead, the templates are coarsely cut loose from the paper printout, arranged by hand, and glued down on a sheet of the material to be used, in this case a sheet of posterboard.

Do Not Disturb

2008-12-09T11:22:00.001-08:00

In general, each weaver added to the work means two more free ends.

Template Printout

2008-12-09T11:16:00.001-08:00

These are the templates for the small-scale cardboard maquette of "Olivier's Fingertip." They were printed from a pdf onto 11" x 14" sheets of paper, and then taped together in a three-wide roll. The weaver on the lower left is the longest one.

Computer-Designed Hexagonal-Weave Basket

2008-12-07T09:31:00.000-08:00

My sculpture, Olivier's Fingertip, is an accurate representation of the tip of a particular man's left index finger (3D data courtesy of IMATI, INRIA, and TECHNION by the AIM@SHAPE Shape Repository.) Olivier's Fingertip is an open hexagonal weave of 43 specially-shaped weavers. There are no splices in the weavers and no closed loops. All of the weavers run from boundary-edge to boundary-edge. Patterns for the weavers were made with Processing, inkjet-printed on paper, transferred to aluminum flashing, and finally cut out and woven by hand.

Examples of weaver templates used to cut out and color-code the weavers are shown.

Weaving and Computer Graphics

2008-03-14T08:29:00.000-07:00

Any object that can be displayed on a computer can be woven. This surprising fact is a consequence of the deep relationship between triaxial weaving and the triangle-faceted surfaces used in computer graphics. To reveal the weave design lurking behind a triangulated surface, just decorate all of the triangles with a crossover pattern. Here the crossover pattern of an open triaxial weave has been used.

Underlying models provided courtesy of IMATI, INRIA, and TECHNION by the AIM@SHAPE Shape Repository.