In this paper, we solve three geometric problems, including the ranking, convex hull and closest pair problems, under the broadcast communication model. To solve these problems, we propose a general scheme, the p-division approach, which is based upon the divide-and-conquer strategy. In the 2-dimensional space, the time complexities of our algorithms for solving these problems are all , where n is the number of input points and p is the number of processors used. Furthermore, our algorithms are all conflict-free and optimal. In the k-dimensional space, k¡Ù3, our ranking algorithm requires time.

Keywords: broadcast communication, computational geometry, parallel algorithm, divide-and-conquer, conflict-free

Retrieve PDF document (199905_04.pdf : 70,163 bytes)

Received April 11, 1996; accepted May 1, 1998.
Communicated by Wen-Lian Hsu.
^*This research work was partially supported by the National Science Council of the Republic of China under contract NSC-82-0208-M-110-027.