# Cover sphere's surface with triangles of geodesic distance edges

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.

• Do you get to add points to your original set to give yourself more possible vertices? For example, if the original set is empty, you will need to add some points. – Ben McKay Nov 8 '16 at 15:36
• No, you can not add more points. Given the empty set, there is no solution, as your triangles (empty set) do not cover the sphere. But if you have any idea while adding points I would be glad to heat it – paramar Nov 8 '16 at 15:40
• If all of the points lie in the same hemisphere, then any edge between them which is minimal lies in that hemisphere too. Hemispheres are geodesically convex. Take the convex hull of your point set in that hemisphere. If more than three points lie on the convex hull, there is no such triangulation. I suspect that necessary and sufficient conditions are complicated. – Ben McKay Nov 8 '16 at 15:53
• @paramar: I assume that you mean a covering by triangles with disjoint interiors. – Ivan Izmestiev Nov 28 '16 at 16:28

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.