Parallel algorithms for geometric searching problems

Computational Geometry is concerned with the design and analysis of computational algorithms which solve geometry problems. In this paper SIMD-MCC algorithms for solving geometric searching problems such as the point domination, the point maxima, the range searching, and the closest point problems are designed by using the parallel divide-and-conquer technique. The computational complexities of all these algorithms for N input points in the k-dimensional space are O(CkN0.5), where Ck = (20.5 + 1)k-2.