This paper considers the problem of finding minimal length tree networks on the unit sphere ℝlsquo; of a given point set (𝒱) where distance is measured along great circular arcs. The related problems of finding a Steiner Minimal Tree SMT(𝒱) and of finding a Minimum Spanning Tree MST(𝒱) are treated through a simplicial decomposition technique based on computing the Delaunay Triangulation DT(𝒱) and the Voronoi Diagram VD(𝒱) of the given point set. O(NlogN) algorithms for computing DT(𝒱), VD(𝒱), and MST(𝒱) as well as an O(NlogN) heuristic for finding a sub-optimal SMT(𝒱) solution are presented, together with experimental results for randomly distributed points on ℝlsquo;.
