Shortest paths on PL surfaces
It's obvious until it isn't.
[Originally posted on TypePad in March 2006. I have updated dead links, reformatted references, and added a footnote.]
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 example1 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 [SICOMP 1987], later refined by Chen and Han [SOCG 1990], and even more recently implemented by Surazhsky et al. [SIGGRAPH 2005]. 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 [COCOON 2002] 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.
Added later: These geometric exampes should be credited to Alexandrov’s 1941 paper where he proves his theorem about nets of convex polyhedra. Alexandrov’s Figure 1 shows the first two of an infinite sequence of nets for the regular tetrahedron; my “toilet paper tube” is equivalent to a later net in this sequence. Figure 2(a) shows a non-standard net of a tetrahedron that cannot be embedded keeping every face flat. Figure 2(b) shows the canonical net, and Figure 2(c) shows the edges of the first net as geodesics on resulting tetrahedron.
