Ernie's 3D Pancakes

Null Homey Topic

Professor Essiness got the smooth Ricci flow, yo.

[via Neatorama]

Chaos in the palm of your hand

[via Neatorama]

Ornament

Start with a a degenerate convex polyhedron with two faces, both regular pentagons, one red and the other green. Starting at the center of one facet (drawn here as a white circle), in every possible direction, extend a geodesic outward in that direction until it intersects itself or hits one of the vertices (drawn as colored circles). A geodesic is a straight path that wraps around edges as though the two sides were laid flat on either side of that edge. Now unfold all the resulting geodesics into the plane as straight line segments. The resulting star-shaped region is bounded by segments of lines through the origin and arcs of circles through the origin. Print onto Shrinky Dink plastic; bake for 2½ minutes at 350° under adult supervision; let cool for 1 minute; throw at ninja hiding behind the Festivus pole.

Aw, shucks.

Doron Zeilberger thanks me for my snide remarks!

See also Aek Thanatipanonda's further hopping.

Update 9/9: Greetings, carnivalleros!

Recursion trees

In response to David's New Yorker visibility graph, I present the perfect illustration of the wrong way to do structural induction—Page 15 of the infamous Codex Seraphinianus.

Mmmm....Spherical goodness.

Ze Frank talks about Grisha Perelman refusing the Fields Medal.

“In your face!” “No, in your face!”

Henry Segerman, a.k.a. Seifert Surface (ahem), builds a hypercube boundary house in Second Life. Mauritz Escher, Robert Heinlein, Andrzej Sekula, and Alexandr Danilovic Aleksandrov would all be proud.

[via BoingBoing]

This is a fib.

A
Short
Poem,
Expanding
Exponentially,
Syllables accumulating,
Reproducing like Fibonacci's horny bunnies.

(Gregory proposed it (but not first); Suresh and others have written more examples.)

Overhang

Suresh describes two of the nicest talks at SODA today: Rakesh Vohra's fascinating account of how to accurately predict the past (sic), and Seshadri Comandur's talk on self-improving algorithms. But in my opinion the nicest—or at least the sillest—talk of the day was by Uri Zwick.

Suppose we have a set of n SODA proceedings that we'd like to stack on the edge of a table, so that the stack reaches as far past the edge of the table as possible. How much overhang can we get? To keep the problem somewhat tractable, let's restrict the problem to two dimensions and pretend the proceedings are long, thin, frictionless, horizontal rectangles.

Anyone who's had a discrete math class has seen a way to stack the books so that the top book hangs out Θ(log n) book-lengths from the edge of the table.

This harmonic construction is often implicitly assumed to be the best possible, but that's only true if the books are stacked one on top of the other. If more than one book can rest on another book, it is possible to get more overhang from the same number of books. But just how much?

Mike Paterson and Uri Zwick described the following simple “brick wall” construction. For any positive integer k, a k-slab is a portion of a brick wall with 2k-1 rows, alternating between k-1 and k bricks long. For example, a 1-slab is a single row of two bricks; a 2-slab is a row of 3, a row of 2, and a row of 3. A 0-stack is a single brick, and for any positive integer k, a k-stack is a k-slab on top of a (k-1)-stack. A k-stack contains Θ(k^3) bricks and has overhang (k+1)/2. In other words, with n bricks, this construction achieves an overhang of Ω(n^1/3)—exponentially more than the harmonic stack!

It's not immediately obvious that every k-stack is stable, but Paterson and Zwick give a nice inductive proof. More generally, they show that it is possible to automaticlaly check whether any given stack of books is stable, by checking whether a certain related linear program is feasible. At the end of his talk, Uri reported that he and several co-authors have proved that this construction is asymptotically optimal—the overhang of any stable stack of n books is at most O(n^1/3)—but we'll have to wait for SODA 2007 to find out why.

In a fit of ironic justice, the talk was scheduled in the smallest of the three conference rooms. Despite crowding tight enough to give any fire marshal (or audience member) heart palpitations, Uri's audience overflowed several yards out into the hallway.

I'm a frayed knot.

The Great Gazoo asks a fantastic question:

How is what you do as a computational geometer different than what a topologist does? Or is it different?

I tend to think of myself a computational topologist these days. Computational topology sits in the intersection of—or in the wilderness between—several different fields, including classical (usually combinatorial, geometric, and/or algebraic, usually low-dimensional) topology; geometric group theory; graph theory; dynamical systems; algorithms and computational complexity theory; optimization; graphics, visualization, and geometric modeling; robotics; and (of course) discrete and computational geometry.

As I hope the abundance of links in the previous paragraph suggests, computational topology is a big and thriving field with a long history. In my opinion, the field certainly dates back at least to Dehn's 1911 algorithm for testing whether a cycle on a surface is contractible, or perhaps even to Dehn and Heegaard's 1907 algorithmic proof of the surface classification theorem. (It's rather remarkable that Dehn and Heegaard's definition of "surface"—a space constructed by gluing triangles together along common edges—so closely matches current practice in geometric modeling!) It's true that Dehn and Heegaard didn't analyze their algorithms, but the algorithmic character of these early results is inarguable. (Analysis of topological algorithms dates back at least to 1961, when Haken proved that knot triviality can be decided in at most quadruply-exponential time.)

My tiny little corner of this field is closest to computational geometry. The types of questions I work on are influenced by my amateur interest in doing "real" computational things with surfaces, like cut them into simpler pieces, paint them with bricks, or morph one into the other, and topology is a natural tool for those sorts of questions. But I'm not as interested in expanding the frontiers of topology itself, nor am I really qualified to do so. I wouldn't dare call myself a topologist without putting the word "computational" in front. Sure, I can spell "cohomology", and on a good day I can even use it correctly, but I don't really know what it means. On the other hand, I imagine most card-carrying topologists who do computational stuff would be hesitant to call themselves algorithmists, or algorithmeticians, or algorists, or dancers-with-former-vice-presidents, or whatever the word is, without using the qualifier "topological". We might be looking at the same problems, drawing the same graphs on the same donuts, and even ultimately using the same mathematics, but our interests and expertise and intuition are probably different.