Problem:


Given:
 A set of points (their coordinates) on a sphere's surface.


Goal:
 Connect them forming triangles, such that:


a)The union of triangles cover the whole surface of the sphere.


b)The length of the edge AB,BC,CA in every triangle ABC corresponds to the geodesic distance between the appropriate points (|AB| = geodesic(A,B))


Does anybody have an idea or a reference? 
My idea was to start with three points. Form the triangle that satisfies b, and continue in its neighbors who already have at least 1 edge with the appropriate length. But I can not see how to guarantee that this construction will eventually cover the whole surface.



Cover sphere's surface with triangles of geodesic distance edges
What you are looking for is a geodesic triangulation of the sphere with a given vertex set $v\_1, \ldots, v\_n$. The following three conditions are equivalent:


1. Such a triangulation exists.
2. The origin lies in the interior of the convex hull of $v\_1, \ldots, v\_n$.
3. Every open hemisphere contains at least one of the points $v\_1, \ldots, v\_n$.


Here are three ways to construct a triangulation.


**Delaunay triangulation:** Take the convex hull of $v\_1, \ldots, v\_n$ and project it onto the sphere by the central projection from the origin. Some of the regions can be convex spherical polygons (if the convex hull had non-triangular faces). Subdivide them by diagonals arbitrarily.


**Stacked or placing triangulation:** Start with a small subset that you can triangulate, and add the other points one by one. If a new point lies inside an old triangle, subdivide this triangle in three. If a new point lies on an old edge, subdivide this edge and both of the adjacent triangles. A small problem is a subset to start with. For points in general position there are four points whose convex hull contains the origin in the interior. Otherwise you might need to start with up to six points.


**Pulling triangulation:** Draw the shortest geodesic arc from $v\_1$ to all the other vertices (if one of them is the antipode of $v\_1$, ignore it). Then draw all those shortest geodesics from $v\_2$ to the other vertices that don't intersect the previously drawn. Proceed.


A good source on triangulations in the Euclidean plane and space is the book "Triangulations" by De Loera, Rambau, and Santos. See especially Chapter 3, "Life in two dimensions". Many constructions for plane triangulations can be adapted to triangulations of the sphere.


