We present a technique for texture mapping arbitrary sphere-like surfaces with minimal distortions by spherical embedding. The embedding is computed using spherical multi-dimensional scaling (MDS). MDS is a family of methods that map a set of points into a finite dimensional domain by minimizing the difference in distances between every pair of points in the original and the new embedding domains. In this paper spherical embedding is derived using geodesic distances on triangulated domains, computed by the fast marching method. The MDS is formulated as a non-linear optimization problem and a fast multi-resolution solution is derived. Finally, we show that the embedding of complex objects which are not sphere-like, can be improved by defining a texture dependent scale factor. This scale is the maximal distance to be preserved by the embedding and can be estimated using spherical harmonics. Experimental results show the benefits of the proposed approach.