[stevenanthony]

The Delaunay triangulation of a set of points on the sphere is given by the convex hull. The Voronoi vertices on the sphere are given by the facet normals and vice versa. The convex hull is quite fast to compute.