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.

Comments

Is there something known about (1+\epsilon)-approximate shortest paths? Even constant factor approximations? It seems that at least some of the issues, e.g. the numerical onese, can be bypassed if we only want an approximation.

[JeffE]

Yes, the numerical issues vanish, but the complexity issues are still there. If the toilet paper roll is long enough, even c-approximate shortest paths from one end to the other cross the long edges arbitrarily many times. So we have to accept either an output-size term in the running time, a compressed output reprsentation (of a form yet to be determined), or just the (approximate) distance instead of a path.

[Jonathan Shewchuk]

I'm confused about what you mean by "isometric to a tetrahedron." I'm pretty sure the (very cool) toilet paper tube example can't be embedded as the surface of a tetrahedron in 3D using Euclidean distances. So what sort of tetrahedron is the toilet paper tube "isometric" to?

[JeffE]

Sure it can. Go get a REAL toilet paper tube, REALLY squeeze the ends together, and see for yourself! (Make sure you squeeze in different places, or you'll get a doubled rectangle instead.) The original edges of the toilet paper tube will spiral around the resulting tetrahedron, like the last picture above.

[JeffE]

And when did you cut your hair?

[Jonathan Shewchuk]

But let's look at your figure of the tetrahedron with the spiral path around it. I claim that the spiral is not the shortest (Euclidean geodesic) path. Imagine a snail starts at the top point of the spiral path and is crawling down the spiral to get to the bottom point. Soon, the snail reaches one of the two faces that contain the bottom point of the spiral path. At this moment, the snail can crawl in a straight line to the bottom point, and get there faster than if it followed the spiral path, because a straight line is the (3D) Euclidean shortest path.

More generally, if you give me a path on the surface of a (3D Euclidean geometric) tetrahedron that traverses some face more than once, I can replace it with an equally short or shorter path that visits each face just once. I record the first point of entry and last point of exit on the face, and replace whatever path is between them with a straight line.

Your flattened-out picture of a toilet paper tube gets around this because it can't actually be folded into a 3D tetrahedron. The top and bottom blue edges are magic teleporters that create paths shorter than a "straight line".

In conclusion, I think your example of a spiral on a (3D geometric) tetrahedron can only be a shortest path if your metric is non-Euclidean, and I cut my hair in August.

[Jonathan Shewchuk]

By the way, I think the shortest-paths-on-PL-surfaces problem is fascinating, and I really enjoyed your post. My quibbling above is just my attempt to make sure I haven't misunderstood anything.

[JeffE]

Ah, I see the problem. You're absolutely right, the blue spiral path isn't a shortest path—sorry if I suggested it was. But it is a geodesic; any sufficiently small subpath of the blue path is a shortest path. Specifically, the blue path is the result of gluing the two straight blue edges together on the original trapezoid in the second figure.

The red path on the toilet paper tube IS a "straight line". So is the blue path. Unlike in the plane, there can be an infinite number of straight lines (ie, geodesics) between any two points in a PL surface, only one of which (generically) is shortest.

The toilet paper tube can be folded into a tetrahedron, but only by folding along geodesics that are not edges in the original triangulation. Those extra folds do not change the intrinsic metric of the surface. To use your example, an ant walking on the surface of the tetrahedron can't tell that it's not on the toilet paper tube. The ant can't see the edges; a small neighborhood of a point on an edge looks exactly the same as a small neighborhood of a point in the middle of a face—they both look like a small piece of the Euclidean plane. Only the vertices look weird. They're just two different pictures of the same metric space.

[Piggy]

What happens if you allow the dimension to be very large? Are you saying you still can't embed these PL surfaces in very large dimensional euclidean space?

That seems odd to me. It seems like I'd have enough room in say R^(3n) where n is the number of triangles.

Pig

[Piggy]

Never mind. I'm a moron.

[Jonathan Ray]

If I understood all this correctly, which is unlikely, I suspect the special case where the points are on the same triangle is not significantly simpler than the general case of finding the shortest path between any two points on a PL surface. I could construct arbitrarily large PL surfaces where the shortest path between two points on the same triangle would have to visit every other triangle in the surface many times. The simulated wavefront solution is cute but painfully obvious. I'm interested to see if anyone finds a better way.

[JeffE]

"I could construct arbitrarily large PL surfaces where the shortest path between two points on the same triangle would have to visit every other triangle in the surface many times."

Yep. Just refine the toilet paper tube.

"...cute but painfully obvious."

Ah, but the devil is in the details! Simulating the wavefront efficiently requires several nontrivial ideas, even for convex embedded surfaces. Read the papers by Mitchell, Mount, and Papadimitriou [SIAM J. Computing 1987], Chen and Han [IJCGA 1996], and Surazhky et al [SIGGRAPH 2005] before dismissing this method so quickly.

In any case, this is essentially the only method we have!

[Jonathan Ray]

The one by Mitchell, Mount, and Papadimitriou is behind a paywall.