Shortest-path Distances Determining the Metric? The metric of a Riemannian manifold determines the shortest
distance between any two points.


*

*I assume the reverse holds?  That is, if you are given the
shortest distance d(x,y) between every pair of points
of a manifold M, the metric for M is determined?
I am mainly interested in compact, connected, closed 2-manifolds,
but the most general answer would be appreciated.
(Apologies in advance for my naivete.)

*Assuming I am correct above, is there some natural subset
S of M such that knowing d(x,y) between every
pair of points of S uniquely determines the metric (up to isometry)?
For example, suppose S is a simple closed geodesic on
M?  Perhaps some assumptions on M are necessary:
genus zero, convex, ... ?
 A: Concerning the second question. A single closed geodesic is not enough. For example, let $S$ be the equator of the standard sphere. All distances between points of $S$ are realized by paths in $S$, so you don't have any information about the metric outside $S$, except that it is sufficiently large (so that the paths outside $S$ are not shorter). 
On the positive side, for every 2D Riemannian manifold, you can construct an embedded graph $S\subset M$ such that the distances between its points determine the metric uniquely (up to an isometry). It suffices to take a union of small geodesic circles such that their encircled regions cover $M$ and lie within convexity radii of their centers. Indeed, a metric on a 2-disc whose boundary is convex and whose geodesics are all strictly minimal, is uniquely determined by the distances between boundary points.
This used to be a long-standing conjecture and was proved in 2005 by Pestov and Uhlmann:
"Two dimensional compact simple Riemannian manifolds are boundary distance rigid", Ann. of Math. 161  (2005),  no. 2, 1093--1110; MR2153407 (2006c:53038).
In higher dimensions, the full conjecture is still open. Until very recently, it was known only for very special metrics (some locally symmetric ones and some splitting ones). Dima Burago and I proved it for sufficiently small regions in any Riemannian manifold, where "sufficiently small" actually means that the diameter is small relative to the maximum modulus of sectional curvature (and of course to the injectivity radius). This is in our paper "Boundary rigidity and filling volume minimality of metrics close to a flat one", Ann. of Math. 171 (2010), no. 2, 1183--1211.    
So, as Will Jagy suggested in his answer, you can take the $(n-1)$-skeleton of a sufficiently fine triangulation for $S$.
I am not aware of any numerical algorithms for this problem. It is known that the solution is stable (depends continuously on the input data) but you have to take into account the derivatives of the boundary distance function. A $C^0$ approximation of the distances is not enough to find an approximation of the metric, see Paul Siegel's answer.
A: You are thinking in terms of long geodesics, but your question is local. The metric is defined point by point. To know the metric tensor at a point $A,$ it is only necessary to know the geodesic distances from $A$ to all points  in an arbitrarily small ball (germ) around $A.$ As to your second question, $S$ would need to be a fairly large set, as on $C^\infty$ manifolds one can alter the metric in a tiny ball (disk in dimension 2) without this being noticeable from far away. It may be that your set $S$ could be a finite set of triangulations, such that every point is in the interior of at least one simplex from at least one triangulation. So the idea, and I am not sure, is a Riemannian metric in the interior of a simplex determined by all pairwise distances between points on the boundary? If so, recovering the metric from such information is seriously nontrivial. But proving or disproving uniqueness is a smaller problem.
A: There are other people who frequent MO who are much better equipped than me to answer your question, but I think I can provide a few useful insights.
First, you are correct that the Riemannian metric can be recovered from the distance function that it induces.  As Will pointed out this is a purely local problem.  First note that not every distance function comes from a Riemannian metric - there are lots of very strong necessary conditions.  One necessary condition is that given any point $p$ and any tangent vector $v$ at $p$ there is a unique smooth curve $c(t)$ defined for values of $t$ in $(-\varepsilon, \varepsilon)$ such that $c(0) = p$, $c'(0) = v$, and $c$ is a length minimizer for any pair of points in its image.  The norm of $v$ can be recovered by differentiating the distance from $p$ to $c(t)$ at $t = 0$, and the inner product on the tangent space at $p$ can be recovered from the norm.
Your second question has some very illuminating and extremely deep answers, but you need additional assumptions and you generally have to be satisfied with slightly weaker conclusions.  The sorts of assumptions you need to make generally involve placing bounds on the sectional curvature of the manifold, and the conclusions usually at best tell you that your metric is uniformly close to another one (such theorems are more useful in the noncompact case).  To illustrate why you can't do better, imagine taking your favorite surface with its standard metric, cutting out a tiny disk, and attaching a huge hot air balloon style bulb to the hole that remains.  Shortest curves between points outside the disk will stay away from the bulb, and so your knowledge of the geometry of the surface away from the bulb won't even determine the topology let along the geometry on the bulb.  Additional assumptions such as curvature bounds help eliminate these examples.  Taking this idea to its extreme, you get results like the Mostow rigidity theorem which says that if a Riemannian manifold of dimension 3 or higher has constant negative curvature then the metric is determined by the fundamental group.  So in that case you can take the set $S$ to be empty.
If you have some other ideas in mind, try to flesh them out as much as possible and maybe Sergei Ivanov or Anton Petrunin will spot your question.
A: Nice paper, I was not aware of it. There is this paper: 
I.G. Nikolaev, A metric characterization of riemannian spaces, Siberian Advances in Mathematics, 1999, v. 9, N4, 1-58 
see the mathscinet page: 
http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=Nikolaev&s5=metric%20characterization&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq
Citing from the Abstract: "We present a metric characterization of Riemannian spaces: a locally compact metric space with intrinsic metric in which geodesics are locally extendable, 
and which has Holder-continuous curvature as a metric space, is isometric with a C^2-Riemannian manifold."
Edit [by J.O'Rourke]. Following Willie's advice (in the comments), here is the MathSciNet link.
A: There is an old paper of mine called "On the Differentiability of Isometries" in which I show that if you know a Riemannian manifold $M$ only as a metric space, i.e., you just know its point set and the metric function $d(x,y)$, then from that information you can recover first the differentiable structure and then the Riemannian metric tensor (i.e., the inner product on each tangent space). I think that answers your first question. The paper is downloadable from here:
http://www.ams.org/proc/1957-008-04/S0002-9939-1957-0088000-X/S0002-9939-1957-0088000-X.pdf
