17
$\begingroup$

Let $M$ be a complete Riemannian 2-manifold. Define a subset $C$ of $M$ to be convex if all shortest paths between any two points $x,y \in C$ are completely contained within $C$. For a finite set of points $P$ on $M$, define the convex hull of $P$ to be the intersection of all convex sets containing $P$. It is my understanding that this definition is due to Menger.

In the Euclidean plane, the convex hull of $P$ coincides with the minimum perimeter polygon enclosing $P$. This does not hold on every $M$. For example, the convex hull of four points on a sphere that do not fit in a hemisphere is the whole sphere (this is Lemma 3.4 in the book below), different from the minimum perimeter geodesic polygon:
           Quad on Sphere
The shortest path connecting $a$ and $b$ goes around the back of the sphere, but the illustrated quadrilateral is (I think!) the minimum perimeter polygon enclosing $\lbrace a,b,c,d \rbrace$.

My specific question is:

Q1. Under what conditions on $M$ and on $P$ will the convex hull of $P$ coincide with the minimum perimeter geodesic polygon enclosing $P$?

I am teaching the (conventional, Euclidean) convex hull now, and it would be enlightening to say something about generalizing the concept to 2-manifolds. More generally:

Q2. Which properties of the convex hull in $\mathbb{R}^d$ are retained and which lost when generalizing to the convex hull in a $d$-manifold?

(The earlier MO question, Convex Hull in CAT(0), is related but its focus is different.) I recall reading somewhere in Marcel Berger's writings that some questions about convex hulls of just three points in dimension $d > 3$ are open, but I cannot find the passage at the moment, and perhaps he was discussing a different concept of hull...

Added: I found the passage, in Berger's Riemannian geometry during the second half of the twentieth century (American Mathematical Society, Providence, 2000), p.127:

A most naive problem is the following. What is the convex envelope of $k$ points in a Riemannian manifold of dimension $d \ge 3$? Even for three points and $d \ge 3$ the question is completely open (except when the curvature is constant). A natural example to look at would be $\mathbb{C P}^2$, because it is symmetric but not of constant curvature.

(Caveat: These quoted sentences were published in 2000.)

Thanks for pointers and/or clarification!

C. Grima and A. Márquez, Computational Geometry on Surfaces: Performing Computational Geometry on the Cylinder, the Sphere, the Torus, and the Cone, Springer, 2002.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ About open question for convex hulls of three points, the following is probably not what you had in mind but I find it an interesting question (open as far as I now). Question: given three generic points on the boundary of the complex hyperbolic plane, does their convex hull fill the plane? $\endgroup$
    – Benoît Kloeckner
    Commented Oct 1, 2011 at 16:45
  • 1
    $\begingroup$ @Benoît: Nice question! I did find the passage I could not remember earlier, and now updated the end of my posting to include it. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 1, 2011 at 17:51
  • 1
    $\begingroup$ @Benoit: The answer to your question is that the convex hull of a finite subset of the ideal boundary of the complex-hyperbolic space never fills the entire space. This is a special case of Anderson's theorem quoted below by Belegradek. Let $X$ be a Hadamard manifold of negatively pinched curvature and $C$ is a closed subset of its ideal boundary. Take the closed convex hull $H$ of $C$ in $X$. Then the ideal boundary of $H$ equals $C$. On the other hand, the situation in the case of non-positively curved symmetric spaces is quite different... $\endgroup$
    – Misha
    Commented Apr 16, 2012 at 5:30
  • 1
    $\begingroup$ On a side note - I don't think the quadrilateral in the figure is the minimum perimeter enclosing polygon. If the arc connecting a and b passing through c is more than 180 degrees (as it seems from the figure and from the question), then the minimum perimeter enclosing polygon would be much larger, passing on the other side. However, I do think it is the minimum area enclosing polygon. $\endgroup$
    – Yellows
    Commented Jan 21, 2020 at 18:36

3 Answers 3

Reset to default
16
$\begingroup$

Q1. For sure simply connected complete and curvature $\le 0$ is sufficient. It is also true for any complete metric on $\mathbb R^2$ without conjugate points.

Q2. Almost no properties survive. I saw only one application of the convex hull in the Riemannian world. This is Kleiner's proof of the isoperimetric inequality in 3-dimensional Hadamard space. It used the following fact:

If $K=\mathop{\rm Conv}(X)$ then the Gauss curvature (i.e. the product of the principle curvatures) of $\partial K$ at any point $p\notin X$ is zero.

Concerning the convex hull of a three point set: generically, it has interior points in all dimensions; see my answer here.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Anton: Thank you for this knowledgeable answer! I am especially intrigued by the no-conjugate-points condition. That almost no hull properties survive in higher-dimensional manifolds is disappointing, but enlightening. Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Oct 1, 2011 at 1:52
7
$\begingroup$

See Jeff Cheeger and David Ebin, Comparison Theorems in Riemannian Geometry. Anton posted while I was typing, and Anton is an honorable man. The reason Q1 works as advertised is in the area of Toponogov's theorem, which tells how quickly two geodesics leaving a point must meet up again if sectional curvatures are positive. With $K \leq 0,$ the two geodesics are allowed to get farther and farther apart, and will do so if the manifold is simply connected. Remember, though, that the 2 dimensional torus has a flat metric $K=0$ and the higher genus oriented closed surfaces have metrics with $K=-1.$ In such cases, you still talk about geodesically convex neighborhoods of a point, when two points are joined by a geodesic arc that stays within the neighborhood, ignoring the possibility of geodesics that leave the neighborhood and return. This notion is also used in Lorentzian, pseudo-Riemannian manifolds.

EDIT: as this is for a class, it seems to me that the flat torus is a good example to go through, one can draw it as a square with identifications. Two distinct geodesics that meet once meet infinitely often, with various possibilities for the picture: in one case, take two closed orthogonal geodesics parallel to the edges of the square. As to points of the torus, they meet once, but as far as arc length parametrization of two curves, they meet infinitely often. The more typical picture is two geodesics at different irrational slopes, the set of intersection points should be dense in the torus.

EDIT TOOO: you have all those computer graphics, you could do convexity in the Poincare disk model of the hyperbolic plane. Then it is the quotients where convexity falls apart,

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

http://en.wikipedia.org/wiki/Fundamental_polygon#Fundamental_polygon_of_a_compact_Riemann_surface

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ shakespeare-navigators.com/JC_Navigator/JC_3_2.html#speech30 $\endgroup$
    – Will Jagy
    Commented Sep 30, 2011 at 21:38
  • $\begingroup$ @Will: Methinks there is much reason in your sayings! :-) $\endgroup$
    – Joseph O'Rourke
    Commented Sep 30, 2011 at 23:32
  • $\begingroup$ Thanks. Although that was just about Anton being honorable... what you are looking at is more or less opposite of Toponogov. With nonpositive sectional curvatures, two geodesics leaving a point do diverge for a time, see davidpbrown.co.uk/poetry/robert-frost.html but one needs a hypothesis of simple connectedness to say it continues that way. In the very special case of dimension 2 and constant curvature, we need make little distinction between topology and the process of taking quotient spaces, in essence wrapping a space around so geodesics now bang into each other. $\endgroup$
    – Will Jagy
    Commented Sep 30, 2011 at 23:40
7
$\begingroup$

Convex hulls are extremely useful in hyperbolic/negatively curved geometry (in particular, I disagree with Anton's bold accessment in his answer that convex hulls have few applications in Riemannian world). Search on the phrases "convex core" and "hyperbolic manifold" to see how convex hulls help to work with Kleinian groups and (non-simply-connected) hyperbolic manifolds.

In the simply-connected case there is the following basic fact: if two convex sets $A$, $B$ in the hyperbolic $n$-space intersect, then the convex hull of $A\cup B$ is contained in the $\Delta$-neighborhood of $A\cup B$, where $\Delta$ is the thin triangle constant for the hyperbolic plane. (See e.g. Lemma 2.12 of this paper by Baker-Cooper). This illustrates fundamental difference of hyperbolic and Euclidean geometry.

One place where convex hulls appear prominently is the paper "The Dirichlet problem at infinity for manifolds of negative curvature" by Michael Anderson, JDG (1983), 701-721. My personal favorite application of this work (derived by Bowditch) is that in a simply-connected manifold of pinched negative curvature the convex hull of any quasi-convex set $Q$ is within bounded Hausdorff distance of $Q$. Surprisingly, this result requres that the curvature is pinched negative and not merely negative.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ @Igor: This is quite useful! Baker and Cooper call their main theorem the "convex combination theorem," which is a useful contrast to Euclidean convex combinations. I also like Proposition 2.5: "convex hulls are convex." :-) Thanks! $\endgroup$
    – Joseph O'Rourke
    Commented Oct 1, 2011 at 16:10
  • 1
    $\begingroup$ @Joseph: I am not sure what you mean by "Euclidean convex combination". The "combination" of Baker-Cooper stems from Klein-Maskit combination of discrete groups, which tells when the group generated by two discrete groups is discrete. $\endgroup$
    – Igor Belegradek
    Commented Oct 1, 2011 at 20:40
  • 1
    $\begingroup$ @Igor: Yes, thanks, I realize the "convex combination" is rather different in the two contexts, so different as to only share the name. $\endgroup$
    – Joseph O'Rourke
    Commented Oct 2, 2011 at 0:40
  • $\begingroup$ @IgorBelegradek I looked at Bowditch's Duke (1995) paper, where in Corollary 2.5.3 he proves that if $Q \subset X$ is closed, then $hull (Q) \subset X$. Is it known if such a result is true at the level of geometrically finite quotients $\Gamma \backslash X$? More strongly, if we consider a closed set $Q$ in $\Gamma\backslash X$, will its convex hull still be within bounded distance of $Q$? Among other things, I am trying to understand the following: suppose you take the thick part of the convex core of $\Gamma \backslash X$. What happens to its convex hull? $\endgroup$
    – Y. Paka
    Commented Jan 16 at 5:39
  • $\begingroup$ @kobeahibe Since in $X/\Gamma$ there are may be many geodesics joining two given points, one has to first agree what is meant by "convex". For example, if you take into account all geodesics, you get the notion of "total convexity", and if you only take into account shortest geodesics you get something else. Even then I don't know anything good about the convex hull. I think this notion is most useful in the universal cover. Whatever you do in the quotient should be translated into the universal cover. $\endgroup$
    – Igor Belegradek
    Commented Jan 16 at 12:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .