Let $M$ be a $k$-dimensional semi-algebraic manifold embedded in $\mathbb{R}^n$. Assume that $M$ is diffeomorphic to $\mathbb{R}^k$. We are interested in the Euclidean path minimizing distance between two points, $P: M\times M \rightarrow \mathbb{R}$.
1) In general, for a semi-algebraic manifold, the number of geodesics between a pair of points is infinite, e.g. two points on a cylinder have an infinite number of helical geodesics between them. However, we make the assumption that our semi-algebraic manifold $M$ is diffeomorphic to $\mathbb{R}^k$. Due to the non-compactness of $M$, is there a finite bound on the number of geodesics between two points $x,y\in M$? If so, what is the relationship between the degree of the defining polynomials and the number of geodesics?
2) Computing the geodesics involves creating a system of ODEs using the Christoffel symbols. I'm guessing that computing the exact closed form of the geodesics is impossible, even when $M$ is semi-algebraic. However, is there a method of solving the resulting BVP to within some guaranteed error $\epsilon$? If there are only a finite number of geodesics between a pair of points from question 1, is there a method to approximately compute all possible geodesics and thereby select the path minimizing one?
3) What can be said about shape of of $P$? It must be $C^0$, but are there any convexity properties? Let $f$ be some polynomial function of two points in $M$. Can we globally minimize $f(x_1,x_2) + P(x_1,x_2)$ to within some guaranteed error $\epsilon$ over $x_1,x_2\in M$?