Fast Delaunay Triangulation and Voronoi Diagram Generation on the Sphere

We describe a fast surface reconstruction approach that takes random points distributed near the surface of a sphere as input, and generates as output a Delaunay surface mesh and its dual Voronoi diagram of the sphere. The method starts from dividing the sphere surface into several initial triangles and introduces a concept of index sites in order to employ the randomized incremental algorithm to get the Delaunay triangulation. We develop a heuristic point search method which can locate a random point within the current triangle efficiently. This method is very efficient because no additional storage is needed to record the flip history and a new random point insertion algorithm is used. We test the performance on a collection of point sample sets and demonstrate a 30% performance improvement compared to existing O(n log n) 3D randomized incremental algorithms.