Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The Question

Let $M$ be a compact, connected, orientable surface without boundary of bounded genus smoothly embedded in $\mathbb{R}^3$; define the diameter $d_M$ of $M$ as the maximum minimal (geodesic) distance between any pair of points $x,y \in S$. My question is:

What's a good estimate for $d_M$?

To make this question more interesting, let's try to avoid pathological examples. Because this is MathOverflow I'm a little insecure about the best way to say this, but let me try the following: suppose that the surface has fixed area and bounded curvature. For instance, one might require that the Willmore energy $\int_M H^2 dA$ is bounded, where $H$ is the mean curvature. This way we avoid examples like an incredibly long, thin (capped) cylinder which has nearly zero surface area but enormous diameter, or similarly an infinitely thin infinitely long spiral. These types of examples tend to confound estimates that otherwise work pretty well.

To understand the scope of the question it may help to know that I really want to be able to evaluate this estimate (using a 5-year-old laptop, say) for a simplicial approximation of $S$. For this reason, I prefer to work with quantities that can be computed efficiently like surface area, enclosed volume, mean/Gaussian curvature, etc. I'm willing to compute a few eigenvalues of the Laplacian (e.g., the smallest and largest), but I refuse to compute all of them. I'm not terribly excited about estimates that bound $d_M$ from only one side.

One Approach

Here's one idea I had based on some rough intuition about Laplacian eigenfunctions. It works surprisingly well in practice (e.g., within 20% of the actual diameter for a wide variety of example surfaces), but I have trouble saying anything concrete about it.

Let $\phi$ be an eigenfunction of the scalar Laplace-Beltrami operator $\Delta$ on $M$, i.e., $\phi$ has unit $L^2$ norm and satisfies $\Delta \phi = \lambda \phi$ for some eigenvalue $\lambda \in \mathbb{R}$. (I'll adopt the convention that $\Delta$ is positive-semidefinite so that $\lambda \geq 0$.) Then we have

$$ \int_M |\nabla\phi|^2 dA = \int_M \Delta \phi \cdot \phi = \int_M \lambda \phi^2 dA = \lambda \int_M \phi^2 = \lambda,$$

hence $||\nabla \phi||_{L^2} = \sqrt{\lambda}$.

Now consider the "first" nontrivial eigenfunction $\phi$, i.e., the one corresponding to the smallest nonzero eigenvalue $\lambda$. I'm going to make a fairly crude approximation and replace $|\nabla \phi|$ at every point with the value

$$ g := \frac{\phi_\max-\phi_\min}{d_M}, $$

where $\phi_\max$ and $\phi_\min$ are the maximum and minimum (pointwise) values of $\phi$.

Where does this idea come from? The idea is best illustrated in 1D -- consider the circle $S^1$, which we can identify with the interval $[0,2\pi) \subset \mathbb{R}$. In this case the first eigenfunction $\phi$ looks like $\sqrt{\pi}\cos(x)$ -- just one full oscillation as we go from zero to $2\pi$:

alt text

In this case the value $g$ is an overestimate of $|\nabla \phi|$ in some places and an underestimate in others. So, we substitute $g$ for $|\nabla \phi|$ in the first relationship above and get

$$ A g^2 \approx \lambda, $$

where $A$ is the total surface area. Solving for $d_M$ gives us an approximation

$$ d_M \approx (\phi_\max - \phi_\min)\sqrt{A/\lambda}. $$

You'll notice my liberal use of "$\approx$" here, because I haven't been able to establish any hard bounds! But again, keep in mind that however crude the argument may be, this approximation appears to work unreasonably well for "reasonable" surfaces.

Still, it would be nice to be able to say something concrete about this approximation (maybe with additional restrictions on $M$) or to have an alternative approximation with established bounds.

Thanks!

share|improve this question
1  
If your surface is given in practice by a fine enough triangulation, I think there are good graph theoretic algorithms to compute the diameter of the 1-skeleton of your tringulation, if the triangulation is not too coarse, this should be not a too bad approximation of the diameter of your surface. I even suspect that people from the computational geometry community may have devellop efficient algorithms to compute the diameter of a polygonal surface. –  Thomas Richard Sep 20 '11 at 17:10
    
You may be interested in corollary 2.3.1 of Heintze-Karcher's paper `A General comparison theorem with applications to volume estimates for submanifolds.' They give an explicit version of Cheeger's inequality, in that you can put an explicit lower bound on the diameter if you know the length of the shortest geodesic, the volume of the surface, and a bound on the curvature. –  Ken Knox Sep 20 '11 at 17:46
add comment

3 Answers

up vote 2 down vote accepted

I am not sure that computing surface area, volume, curvature, or eigenvalues of the Laplacian, represents the best route. To expand on Thomas Richard's points: The diameter of the 1-skeleton can be found in roughly $n^2$ time, where $n$ is the number of vertices. It is a relatively straightforward algorithm, employing Disjkstra's shortest path algorithm. You can find existing implementations, e.g., this igraph one. It's even a function in Mathematica/Combinatorica: Diameter[g]. It of course would only yield an approximate geometric diameter, depending on the coarseness of your mesh. But you are only seeking estimates anyway. It could definitely run on a 5-year old laptop, because the space requirements of Dijkstra's algorithm are only $O(n)$, which you need already to store your mesh. Whether you can wait out $O(n^2 \log n)$ computation time depends on your laptop's processor (and your patience!). Edit. See comments for approximation algorithms.

I don't know of computational geometry work that computes the true geometric diameter for arbitrary genus. I have written papers on the genus-zero case myself, and already it is intricate: about $n^8$. ("Star Unfolding of a Polytope with Applications," SIAM J. Comput. 26, pp. 1689-1713).

So the best route seems to be computing the diameter of the 1-skeleton of an approximate triangulation. To increase precision, remesh at a finer scale. There are many algorithms available for this, e.g., "Geodesic-based surface remeshing," Sifri, Sheffer, Gotsman.

share|improve this answer
    
I didn't suspect that computing the diameter of a polygonal surface was so complicated. Are there lower bounds on the complexity ? –  Thomas Richard Sep 21 '11 at 7:53
1  
@Thomas: No, no substantive lower bounds are known. To give you a sense of why it seems difficult: For a convex polyhedron, generically the diameter is realized by two points connected by 5 distinct equal-length shortest paths. –  Joseph O'Rourke Sep 21 '11 at 9:53
1  
$n^8$ -- wow! Before this week it never occurred to me how hard it is to get your hands on the diameter of a surface (even approximately). Interesting. Thanks for some nice pointers. My main gripe with Dijkstra-based algorithms is that you can get an arbitrarily bad overestimate (consider a Schwarz lantern with progressively worse triangle aspect ratios). I should also say that I use the diameter to estimate a parameter in an algorithm that is otherwise roughly $O(n)$, so going to $O(n^2)$ or worse is a bit hard to swallow. That's why I'm thinking about quantities like area, volume, etc. –  TerronaBell Sep 21 '11 at 16:23
    
@fuzz: That's why you should triangulate carefully :-). E.g., Delaunay-based meshing. If $n^2$ is too large, then perhaps explore the various approximation algorithms, e.g., "Fast and Simple Approximation of the Diameter and Radius of a Graph": springerlink.com/content/d04125271382j7l3 ; or "On the Power of BFS to Determine a Graph’s Diameter": springerlink.com/content/5nj71uwb2qflwr6n . –  Joseph O'Rourke Sep 21 '11 at 17:11
add comment

This paper of Peter Topping doesn't really meet all of your criteria, but may be of interest to you. For surfaces it bounds the diameter from above in terms of the $L^1$ norm of the mean curvature of the surface.

share|improve this answer
1  
Very nice reference! Didn't know about this one. A bit too conservative, though -- for instance, for surfaces where I know the diameter the upper bound itself overestimates by a factor of about 100 on average. It's interesting to note, however, that if you replace their constant $32/\pi$ with $1/\pi$ (as conjectured for the extrinsic diameter) you still appear to end up with an upper bound. – fuzzytron 6 secs ago –  TerronaBell Sep 21 '11 at 16:42
add comment

This seems highly related to:

http://en.wikipedia.org/wiki/Cheeger_constant

share|improve this answer
    
Thanks Igor. I looked at Cheeger's constant, but it seems to have two problems: first, it's not clear how to compute it efficiently, and second it doesn't really tell you about diameter. For instance, on a cylinder you might think you get a curve whose length is twice the diameter, but you can get a smaller value of length/max(area1,area2) by placing a curve around the "waist" of the cylinder: brickisland.net/cheeger.png –  TerronaBell Sep 20 '11 at 15:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.