A Parallel Delaunay Algorithm Applied in Lunar Rover Stereo Vision System

Abstract—A parallel Delaunay algorithm is implemented to accelerate terrain feature points triangulation procedure in lunar rover stereo vision system. The algorithm uses divide-and-conquer approach and is optimized by employing a new strategy of the merge step. Furthermore, we parallel the algorithm using OpenMP library on a multi-core computer and compare the parallel Delaunay algorithm with traditional one using real terrain feature point data and simulation data which size ranges from 100,000 terrain points to 1,000,000. This paper presents design and structure of the parallel Delaunay algorithm and analyzes its performance. Keywords-Delaunay; parallel; tranglulation; OpenMP; lunar rover;stereo vision I