The Ann Arbor Chronicle » yard waste collection http://annarborchronicle.com it's like being there Wed, 26 Nov 2014 18:59:03 +0000 en-US hourly 1 http://wordpress.org/?v=3.5.2 Packing Pyramids: UM and Ann Arbor http://annarborchronicle.com/2010/02/14/packing-pyramids-um-and-ann-arbor/?utm_source=rss&utm_medium=rss&utm_campaign=packing-pyramids-um-and-ann-arbor http://annarborchronicle.com/2010/02/14/packing-pyramids-um-and-ann-arbor/#comments Mon, 15 Feb 2010 00:41:43 +0000 Dave Askins http://annarborchronicle.com/?p=37711 Ann Arbor is home to the University of Michigan, which makes it different from other similar-sized Midwestern cities lacking a world-class research institution. You can’t swing a dead Greek philosopher without hitting someone in this town who can tell you how significant the connection is between Ann Arbor and UM.

Elizabeth Chen

Elizabeth Chen assembles a tetrahedron from connectors and straws. (Photos by the writer.)

In that way, at least, Ann Arbor is densely packed.

This is a story about that town-gown connection. It’s a story that connects a recent UM mathematics PhD thesis defense to the Ann Arbor planning commission – and takes a continuous path though topics like Klingons, grocery bags, affordable housing, yard waste collection and Valentine’s Day.

We begin with Elizabeth Chen, who successfully defended her PhD dissertation last Friday in East Hall on the UM campus. Her presentation included several hands-on assignments for those in the audience of around 30 people – several of whom assured The Chronicle that hers was an “unconventional” thesis defense.

Chen exhorted the assembled mathematicians to paste together plastic pyramid shapes with gummi putty to help them get an intuitive feel for the shapes: “It’s not so scary!” she admonished them. After half an hour, one member of her thesis committee prodded her to get to the mathematics part – he really had “better things to do.” The Chronicle, however, did not.

Packing Pyramids: Background

Never mind the answers – many of the questions themselves that mathematicians work at solving are completely inaccessible to (even very clever) non-mathematicians. That’s not the case with Chen’s work. Her dissertation title sounds almost like it could belong in the children’s section of a bookstore: “A Picturebook of Tetrahedral Packings.”

Certainly even small children can grasp the basic concept of the question Chen works on: How tightly can you pack pyramids together?

Regular Tetrahedron

Example of a model of a regular tetrahedron in the form of a die. The way you tell which number is "up" on such a die is to look at the one that can be read in its usual orientation. For this one, someone rolled a "4."

The specific kind of pyramid Chen works with is a regular tetrahedron (plural: tetrahedra). Each of the four faces of a regular tetrahedron is an equilateral triangle – one with three congruent sides.

For longer than a little while, it was believed that tetrahedra could be packed together perfectly to fill all of space, leaving no gaps at all. It was Aristotle (384 BC-322 BC), writing in “On the Heavens,” who suggested that regular tetrahedra were space-filling.

But by the 1400s, German mathematician Johannes Müller had countered Aristotle’s claim. And by the end of the 1800s, another German mathematician, Hermann Minkowski, had begun looking at the general problem of packing convex shapes. [A tetrahedron is convex – if you take any two points in a tetrahedron, the straight line connecting those points stays completely inside the tetrahedron.]

In 1900, David Hilbert, also German, included the problem of tetrahedron packing as a special case of Problem 18 in a list of 23 problems he had identified as interesting.  Hilbert’s list has guided much of mathematical inquiry for the last century. From Hilbert’s paper [emphasis added]:

How can one arrange most densely in space an infinite number of equal solids of given form, e. g., spheres with given radii or regular tetrahedra with given edges (or in prescribed position), that is, how can one so fit them together that the ratio of the filled to the unfilled space may be as great as possible?

Already in the early 1600s Johannes Kepler had conjectured that the most efficient way to pack spheres was in a way that Chronicle readers would recognize as the same approach that any produce clerk would take to stacking oranges. What Hilbert was asking for, though, was an actual proof that this was the optimal configuration. That (computer-aided) proof came in 1998 from Thomas Hales, who began his work at the University of Michigan.

9 Tetrahedra gummied together

A cluster of 9 tetrahedra gummied together. Chen's approach to maximizing density involves taking copies of these locally dense clusters and fitting them into lattices.

The density of an optimal sphere-packing is approximately 0.74048. That is, given an infinite number of identically-sized spheres, about 74% of space can be filled up with them – and we know, per Hales’ proof, with 100% certainty that there’s no configuration of spheres that would be any denser than that.

The 0.74048 number is thus a kind of a benchmark against which tetrahedron packing can be measured.

In 1972 Stanislav Ulam, a Polish-American mathematician who worked on the Manhattan Project, conjectured that spheres were the worst-packing of all convex bodies. So from Ulam’s conjecture, it should follow that tetrahedra should pack denser than 0.74048.  But in the mid-2000s, investigations of tetrahedron packing that used computer simulations, as well as experiments using  physical tetrahedral dice, could not establish any configuration of tetrahedron packing that clearly surpassed the 0.74048 for spheres. Maybe tetrahedra were worse-packing than spheres?

Was Ulam wrong? No. We’ll get to that in a moment. Now’s a good chance to think about how very wrong Aristotle had been – wrong about tetrahedra and their ability to completely fill space. How did he manage to massively miss that one?

Part of the reason could have been that Aristotle had no ready source of tetrahedral dice and gummi putty to try pasting models of tetrahedra together – the way that Elizabeth Chen asked the audience of her thesis defense to do. Once you have them in your hands, it’s easy to paste together models and convince yourself that they will fill less than all of space – a pastes-great-less-filling experience.

Alex and Zach

Alex Mueller (foreground) and Zach Scherr (to Mueller's right), both graduate students in mathematics at the University of Michigan, stayed pretty well focused on the hands-on tasks provided by Chen during her thesis defense.

In 2008, Chen showed how to arrange tetrahedra to achieve a packing of around 0.7786 – clearly beating the maximal packing for spheres, and in some sense vindicating Ulam.

Since Chen’s 2008 paper, other researchers have ratcheted the number upward, to 0.855506. But in early January of 2010, in a paper published with Michael Engel and Sharon Glotzer – both faculty in the UM department of chemical engineering – Chen nudged that number a bit higher, to 0.856347. [The more recent activity in the field of tetrahedron packing is succinctly covered in a New York Times article by Kenneth Chang: "Packing Tetrahedrons, and Closing In on a Perfect Fit"]

The January paper’s result, which is not included in Chen’s PhD thesis, was all that some in the audience wanted hear about: “What about the ‘champion’? I want to know how you did it, and then I’m going to leave.”

Chen eventually produced what they were there to see, which was the culmination of her systematic investigation: how individual copies of clusters of tetrahedra can fit densely into lattices. And her committee gave her a passing grade on the thesis defense.

Ann Arbor’s Kind of Density

When the topic of dense packing shows up in the pages of The Chronicle, it’s typically not in the sense of how densely you can pack space with tetrahedra. It’s usually something less esoteric, like a caution from the city’s public services area administrator, Sue McCormick, about packing the city’s yard waste containers too densely with leaves. From a recent Chronicle report on a city council budget meeting:

McCormick cautioned against compacting too many leaves into the containers, as it sometimes made emptying them difficult. [The automated arms tilt the carts upside down – whereupon the contents are liberated from the confines of the cart through a physical attractive force, a so-called "gravity."] McCormick pointed to the benefit of bagging as (i) providing more control, and (ii) limiting the amount of disruption in the community.

Or, if not densely packing leaves, then it’s densely packing people that’s the topic of discussion. We reported resident Lou Glorie’s remarks made during public commentary at a June 2009 city council meeting this way:

She suggested that urban sprawl had been replaced by the desire to pack 1,000 more souls into the downtown of some city. “Concrete is the new green,” she concluded.

Discussion on the merits of planning for greater population density in the city of Ann Arbor has dominated the local political conversation at least over the last decade. So it’s worth noting that a former Ann Arbor planning commissioner, Eric Lipson, attended Elizabeth Chen’s dissertation defense on dense packings of tetrahedra.

Eric Lipson

Eric Lipson, former planning commissioner with the city of Ann Arbor, hold the hands-on materials provided to audience members at Elizabeth Chen's Feb. 12 thesis defense.

Lipson did not attend by random accident. He’s the general manager of the Inter-Cooperative Council, a housing cooperative started in 1932 by UM students. Chen lived in ICC housing, at the Georgia O’Keeffe House, from 2005-2008. She was the O’Keeffe work manager for most of her time there.

That’s how Lipson knew Chen, and knew that her dissertation defense was coming up.

But Chen and Lipson aren’t just linked by the ICC connection.

Lipson himself has a practical interest in geometric shapes. He holds a patent on a connector for construction panels, which can be used to create 10-sided dome-shaped buildings.

And those 10-sided buildings can be shipped flat-packed wherever they might be needed. The company formed to manufacture and sell the product is called DecaDome. Lipson has prototypes set up in his backyard. While the audience was waiting for Chen’s dissertation committee to confer on her presentation, he showed us images of those prototypes from his Blackberry.

DecaDome

Eric Lipson showed The Chronicle images of DecaDome protoypes while we waited for Elizabeth Chen's dissertation committee to confer.

Part of what makes the connector special, said Lipson, is that the opening doesn’t require absolutely perfect alignment in order to accept a panel, which makes the task easier. As far as tools, all that’s needed is a screwdriver – though he allowed that a cordless power screwdriver would be recommended.

Panel material for DecaDomes ranges from foam core, to fluted polycarbonate, to pressure-treated plywood, to foam core panels covered with resin cement and fiberglass mesh.

Klingons

Different kinds of material is also the basis of the Klingon connection to Chen’s thesis. After Chen’s presentation, Sharon Glotzer, a UM professor of chemical engineering, helped clarify for The Chronicle why she and chemical engineering colleague Michael Engel were co-authors with Chen on the world-record tetrahedron-packing paper.

Glotzer and Engel are interested in designing new materials with interesting properties – properties that could, say, affect how we visually perceive objects made from them. That is, they’re interested in materials that have some kind of cloaking property. Glotzer told us that the various tech blogs take their speculations on this kind of scientific work in the direction of the Klingon cloaking device from the Star Trek series. [A cursory look into the Star Trek archives suggests it's the Romulans who pioneered cloaking technology, not the Klingons, who may have simply stolen it, but that's an issue that lies beyond the scope of this article – in any case, the proof is left to the reader.]

The tetrahedron connection to Glotzer’s work is this: Starting with tiny tetrahedra composed only of a few thousand atoms and suspended in a liquid medium, they can self-assemble into ribbon-like lattices. Exposure to light causes these ribbons to twist. And it’s the twist that holds the potential for cloaking. The twist – or chiral property – makes a compound optically active. That is, it will rotate the plane of polarization of light that’s passed through it. Glotzer stressed that the key to these compounds is the starting shape of the nano-particles – it only works with tetrahedra.

Glotzer told The Chronicle that she’s focused on the purely scientific aspect of this work – she’s not hoping someday to run a private company manufacturing cloaking devices.

Groceries and Valentines

Glotzer’s perspective on tetrahedra is not that the densest packing of tetrahedra is the most interesting packing. Rather, it’s that an interesting packing of tiny tetrahedra is the one that results in a larger object with desirable properties.

It’s a similar principle that applies, for example, to packing grocery bags. The goal is not to fit as much as possible into each bag. The goal is to pack each bag so that the resulting larger object – the packed bag – has desirable properties. A commonly desired property of a packed grocery bag is that it will stand up on its own – a property that’s a function more of the way its contents are packed than of the bag itself, something that’s especially true with plastic grocery bags.

And in Ann Arbor, at least, properly packing “square bags” can lead to love. From a 2006 interview with former mayor of Ann Arbor Ingrid Sheldon, in which she describes how she met her husband, Cliff:

HD: So you were a checker at the Kroger in Lower Town and he was a produce clerk?

IS: He was. He was doing his management training. He had just gotten his MBA from Michigan and as a part of his training, he was anticipating going into finance, they had him work in the stores.

HD: So did this unfold … was it the break room, where you first met, or?

IS: It was five o’clock rush. And these were the old columns of numbers, you know, we didn’t have a nine-key or a ten-key. We had columns for one’s and ten’s and hundred’s. I was noted for being very fast! And for packing square bags! I could ring up blind, and do the division 3-for-79 in my head, and you had to just do it. So anyway, I turned around one day, during the five o’clock rush, and there was this scrawny kid, packing round bags slowly. Ugh! So, of course, I had to assist him. But I realized he was youngish and I thought maybe I ought to pursue this guy, and find out more about him, before I totally blow him off! … it was love in the produce aisle! … and we started dating.

Happy Valentine’s Day from The Chronicle.

More Photos

Additional photos from the thesis defense that could not be densely packed into the layout of the above text:

Jeffrey C. Lagarias

Prof. Jeffrey Lagarias, who chaired Elizabeth Chen's dissertation committee.

Julian Rosen with 17-er tetraheadral cluster

Julian Rosen, a graduate student in mathematics, holds the 17-er tetrahedral cluster he pasted together during the dissertation defense.

Igor Kriz,  Professor of Mathematics

Igor Kriz, UM professor of mathematics and a member of Chen's thesis committee.

Elizabeth Chen

Elizabeth Chen distributes materials for the hands-on portion of her thesis defense presentation.

Tetrahedral die held by Professor David Winter

Tetrahedral die held by professor of mathematics David Winter.

Chen receives the verdict

Elizabeth Chen (far right) receives the verdict on the oral defense of her dissertation: she passed. Standing with documents (far left) is her committee chair, Jeffrey Lagarias. Standing to Chen's right around the corner from Chen is professor of chemical engineering Sharon Glotzer.

]]>
http://annarborchronicle.com/2010/02/14/packing-pyramids-um-and-ann-arbor/feed/ 15