« Practice makes perfect. Ish. | Main | Stimpy invents Katamari Damacy »

March 08, 2006


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.


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?


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.


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.


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.


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.



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.


"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.

The comments to this entry are closed.