Ernie's 3D Pancakes

Ernie's are better.

Pat Robertson's Age-Defying Protein Pancakes, best served drenched in the freshly-spilled blood of democratically elected Venezuelan dictators and murderous mind-bending college professors.

[via WFMU, the best damn(ed) radio station on the web]

On the other hand, I cannot predict the future.

I'd suggest it might be better for communities to figure out how to care for all of their members, even the ones who seem inclined to complain. Ignoring the interests of some members of the community to further general harmony (people get to keep doing things the way they want to, advisors can decide how to treat their grad students and other pieces of lab equipment, etc.) is a risky move. Not only might the trouble-makers you're ignoring have valid concerns -- concerns which would do more to ensure long-term harmony should the community heed them -- but, their reaction at being shut out by the community might be ... bad.

Stimpy invents Katamari Damacy

Shortest paths on PL surfaces

Here's a nice open problem that I've only thought about long enough to convince myself that it's interesting. The problem comes out of a common and legitimate criticism of my recent computational topology research, which deals with finding various kinds of minimal graph structures on so-called combinatorial surfaces.

A combinatorial surface consists of an abstract 2-manifold M, a graph G embedded in M so that every face of the embedding is a topological disk, and an assignment of non-negative real weights to the edges of G. Roughly speaking, we only allows paths and cycles that are walks or circuits in the graph G; the length of such a path is defined in the usual way, by adding up the weights of the edges along the path, with the right multiplicity. (If a path π traverses an edge e twice, the length of e is counted twice in the length of π.) Paths that cross through the faces of G are not even considered. This definition includes nonconvex polyhedra—like the Stanford bunny—but the edge lengths don't have to correspond to any nice embedding of the surface. Given two vertices on a combinatorial surface, we can compute the shortest path between them (in G, remember) in O(n log n) time using Dijkstra's algorithm.

Most people who see this model for the first time ask immediately why I'm interested in something so restrictive. What do results in the combintorial surface model imply about “real” surfaces, where paths can go anywhere and path lengths are continuous rather than discrete? As it turns out, most of the topological results seem to generalize without too much trouble, but the algorithmic results are not so accommodating. (There are also some extremely nasty numerical issues, but to keep the discussion focused, let's just assume we are working on a real RAM with square roots.)

Here's a more general and very natural surface model. A piecewise-linear triangulated surface is a collection of n Euclidean triangles, where some pairs of edges (of equal length) are glued together. To keep things simple, let's imagine that each of the 3n triangle edges is glued to exactly one other edge, so that the resulting topological space is a 2-manifold. Anyone who has played with paper models of polyhedra is already used to this definition.

Any PL surface has a natural metric, inherited from the Euclidean triangles: the length of any path is measured by adding up the lengths of the subpaths within each triangle. Consequently, the intersection of any geodesic (or locally shortest path) with a triangle is a striaght line segment, and if a geodesic crosses an edge, it enters and leaves at the same angle. PL geodesics can only “bend” if they go through vertices.

Okay, so here's the open problem: Describe an algorithm to compute the shortest path between two points on the same triangle in a piecewise-linear triangulated surface, where the running time is bounded by a function of the number of triangles.

Pretty simple, huh? Obviously, the shortest path is just a line segment insidee the triangle, right? That's exactly right if the surface can be embedded in some Euclidean space so that every triangle is flat, but not every PL surface has such an embedding. In general, like many “obvious” things, this claim is actually false.

Here's a simple example of a PL surface that has the combinatorial structure of a tetrahedron, but different geometric structure. In particular, there's no way to actually embed this surface in any Euclidean space so that every triangle lies in a plane. Moreover, the three obtuse vertices are all identified to a single point with total angle greated than 2π, so this can't fold into a convex polytope. The red line segments show the shortest path between two points on the "big" face.

In fact, as Gunter Rote observed, the number of times that a shortest path can cross through the same triangle is not bounded by any function of the number of triangles. Here's a simple PL surface I call a “toilet paper tube”. It's made from four long thin triangle, glued in a cycle along their long edges. There's no way to embed this surface so that every triangle lies flat in a plane. The shortest path between the two red vertices crosses through each triangle 3 times. By making the triangles longer, we can replace 3 with any positive integer.

We can compute shortest paths in PL surfaces by simulating an expanding circular wavefront from one of the two points. Whenever the wavefront meets a vertex, an edge, or itself, we update our internal description of how the front intersects the facets of the surface. An efficient version of this method was developed by Mitchell, Mount, and Papadimitriou, later refined by Chen and Han, and even more recently implemented by Surazhsky et al. However, the running time of those algorithms will not be bounded by a function of n, because the wavefront could collide with the same edge arbitrarily many times.

The shortest path problem is open even when the PL surface is isometric to the surface of a 3-dimensional convex polytope, or equivalently by Alexandrov's theorem, if the angles around every vertex in a PL surface sum to at most 2π. For example, take the toilet paper roll and squeeze the ends together into line segments. Voila! A long skinny tetrahedron!

So now let me repeat a very special case of the open problem. Describe an algorithm to compute the shortest path between two vertices of a PL surface consisting of four triangles and isometric to a convex tetrahedron, using a constant number of exact real arithmetic operations (+,-,×,÷,√,<0?). Should be easy, right?

Right?

Even though we have no hope of computing an explicit list of edges crossed by the shortest path, the crossing sequence might have a concise encoding, similar to the grammars used by Schaefer, Sedgwick, and Stefankovic to encode the normal coordinates of a curve on a triangulated surface. More ambitiously, perhaps the entire shortest path structure has a concise encoding, which can be computed on the fly using the wavefront approach. Alternately, perhaps one could quickly find an isometric PL surface—a decomposition of the same PL surface into different triangles—in which any shortest paths can cross each edge only a constant number of times, and then run the usual wavefront algorithms on the new structure.

And here we hit on the crux of the problem—the edges in a PL surface are red herrings. The actual metric is perfectly flat everywhere except at the vertices, where the surface looks like the top of a cone. The edges tell us only where these cone points are located relative to each other, but the choice of edges is not unique. For example, we can glue two triangles together and then cut the resulting quadrilateral into two different triangles. In fact, every PL surface has an infinite number of isometric representations.

There is a canonical choice of edge for any PL surface: the Delaunay triangulation of the cone points. Just like in the plane, the Delaunay triangulation is the dual of the Voronoi diagram of the cone points, and it can be obtained by repeatedly flipping any pair of triangles whose opposite angles sum to more than π until there are no such pairs. Unfortunately, there is no bound on the number of flips required. Somewhat confusingly, the Delaunay triangulation of the surface of a convex polytope need not have the same facet structure as the polytope itself. It's also not necessarily a simplicial complex; triangles can be glued to themselves, and pairs of triangles can be glued together more than once.

Can the Delaunay triangulation of a given PL surface be computed quickly? Can shortest paths in Delaunay PL surfaces be computed quickly? Given two points in the same trangle in a Delaunay PL surface, is the shortest path between them a line segment in that triangle? Is there a PL equivalent of the stereographic lifting map? How many licks does it take to get to the Tootsie Roll center of a Tootsie Pop? How much Zen would a Zen master master if a Zen master could master Zen?

By an amazing coincidence, Michael Nielsen is also thinking about shortest paths.

Practice makes perfect. Ish.

From Eurekalert:

In an experiment in which students either took quizzes or were permitted to study material repeatedly, students in the study-only group professed an exaggerated confidence, sure that they knew the material well, even though important details already had begun slip-sliding away. The group that took tests on the material, rather than repeatedly reading it, actually did better on a delayed test of their knowledge.

From Rate Your Students:

My classes are large, so I mostly use multiple-choice tests. One day, being one question short of a nice round number, I used this question: "The answer to this question is D. Be sure to mark D on your answer sheet." The offered choices were: (A) This is the wrong answer. (B) This is the wrong answer. (C) This is the wrong answer. (D) This is the correct answer. Be sure to mark it on your answer sheet. (E) This is the wrong answer.

About 20% of the students got it wrong.