# Convex hull on a Riemannian manifold

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:

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 written over a decade ago.)

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.

-
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? –  Benoît Kloeckner Oct 1 '11 at 16:45
@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. –  Joseph O'Rourke Oct 1 '11 at 17:51
@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... –  Misha Apr 16 '12 at 5:30

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 convex hull in Riemannian world. This is Kleiner's proof of isoperimetrical inequality in 3-dimensional Hadamar space. It used the following fact:

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

Concerning convex hull of three point set. Generically it has ineriour points in all dimensions; see my answer here.

-
@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! –  Joseph O'Rourke Oct 1 '11 at 1:52

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,

-
–  Will Jagy Sep 30 '11 at 21:38
@Will: Methinks there is much reason in your sayings! :-) –  Joseph O'Rourke Sep 30 '11 at 23:32
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. –  Will Jagy Sep 30 '11 at 23:40

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.

-
@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! –  Joseph O'Rourke Oct 1 '11 at 16:10
@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. –  Igor Belegradek Oct 1 '11 at 20:40
@Igor: Yes, thanks, I realize the "convex combination" is rather different in the two contexts, so different as to only share the name. –  Joseph O'Rourke Oct 2 '11 at 0:40