## Tuesday, September 27, 2011

### Undip as a sculptural language

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.)

## Monday, September 26, 2011

### Learn undip and mutate your own!

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.

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.

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.

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!

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!

## Wednesday, September 21, 2011

### Seen at World Maker Faire New York

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.

## Saturday, September 17, 2011

### Make a Basket from a Word

"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!

## Friday, September 2, 2011

### Custom-designed twogs

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.

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.

## Thursday, September 1, 2011

### Connectedness and polyhedrality

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.

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

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.

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.

Subscribe to:
Posts (Atom)