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 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.
 A: 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 
A: 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.
A: 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.
